Breadth first search (BFS) and its matlab code

---

Preface

   Breadth first search is often compared with depth first search , Both of them are graph search algorithms, but their search methods are different , Next, let's study together ~

---

One 、 What is breadth first search ？

   Breadth first search , Its full name is $BreadthfirstSearch$, Referred to as $BFS$, Also known as width first search . It starts from the initial node , Apply production rules and control strategies to generate the first layer nodes , At the same time, check whether the target node is in these generated nodes . If there is no , Then use production rules to put all The first level nodes are expanded one by one , Get the second level node , And check whether the second layer node contains the target node one by one . If there is no , Then the production rules are used to expand the second layer nodes . Expand in this order , Check it out , Until the target node is found . If all nodes are expanded , No target node is found , There is no solution to the problem .
   The above introduction is from the following website ：

https://blog.csdn.net/ZhuRanCheng/article/details/115588272

Two 、 The basic idea of breadth first search is its matlab Code

1、 The basic idea of breadth first search

   Breadth first search uses queues （queue） To achieve , The whole process can also be seen as an inverted tree ：
  （1） Put the root node at the end of the queue ;
  （2） Take one element from the head of the queue at a time , View all the subordinate elements of this element , Put them at the end of the queue . And record this element as the precursor of its next level element ;
  （3） End the program when you find the element you are looking for ;
  （4） If you traverse the whole tree and haven't found , End procedure .
   The above basic ideas refer to Baidu Encyclopedia ：

https://baike.baidu.com/item/%E5%AE%BD%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2/5224802?fromtitle=%E5%B9%BF%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2&fromid=2148012&fr=aladdin

2、matlab Code

   Breadth first search ：BFS.m

clear all;close all;clc
% Initialize adjacency compression table 
b=[1 2;1 3;1 4;2 4;
   2 5;3 6;4 6;4 7];

m=max(b(:));                % The maximum value in the compressed table is the width and height of the adjacency matrix 
A=compresstable2matrix(b);  % Construct the matrix representation of the graph from the adjacency compression table 
netplot(A,1)                % Image represents 

head=1;             % Queue header 
tail=1;             % Queue tail , The start queue is empty ,tail==head
queue(head)=1;      % Add the first node of the graph to the header 
head=head+1;        % Queue expansion 

flag=1;             % Mark whether a node has been accessed 
re=[];              % final result 
while tail~=head    % Determines if the queue is empty 
    i=queue(tail);  % Take the tail node 
    for j=1:m
        if A(i,j)==1 && isempty(find(flag==j,1))    % If the node is connected and has not been visited 
            queue(head)=j;                          % New nodes are listed 
            head=head+1;                            % Expand queue 
            flag=[flag j];                          % Mark the new node 
            re=[re;i j];                            % Save the edge into the result 
        end
    end
    tail=tail+1;            
end

A=compresstable2matrix(re);
figure;
netplot(A,1)

   Matrix representation of construction graph ：compresstable2matrix.m

function A=compresstable2matrix(b)
    [n ~]=size(b);
    m=max(b(:));
    A=zeros(m,m);

    for i=1:n
        A(b(i,1),b(i,2))=1;
        A(b(i,2),b(i,1))=1;
    end
end

   Drawing function ：netplot.m（ Matrix generates undirected network graph ）

% Function name netplot
% Please input the usage method help netplot
% No return value % Functions can only handle undirected graphs 
% author ：tiandsp
% Last modified ：2012.12.26
function netplot(A,flag)
    % Call method input netplot(A,flag), No return value 
    %A Is adjacency matrix or incidence matrix 
    %flag=1 When dealing with adjacency matrix 
    %flag=2 When dealing with incidence matrix 
    % Functions can only handle undirected graphs 
    if flag==1      % Adjacency matrix represents undirected graph 
        ND_netplot(A);
        return;
    end
    
    if flag==2      % The incidence matrix represents an undirected graph 
        [m n]=size(A);      % Incidence matrix becomes adjacency matrix 
        W=zeros(m,m);
        for i=1:n
            a=find(A(:,i)~=0);
            W(a(1),a(2))=1;
            W(a(2),a(1))=1;
        end
        ND_netplot(W);
        return;
    end
           
    function ND_netplot(A)
        [n n]=size(A);
        w=floor(sqrt(n));       
        h=floor(n/w);        
        x=[];
        y=[];
        for i=1:h           % Make the generated random point have its range , Make the display more widely distributed 
            for j=1:w
                x=[x 10*rand(1)+(j-1)*10];
                y=[y 10*rand(1)+(i-1)*10];
            end
        end
        ed=n-h*w;
        for i=1:ed
           x=[x 10*rand(1)+(i-1)*10]; 
           y=[y 10*rand(1)+h*10];
        end
        plot(x,y,'r*');    
        
        title(' Network topology '); 
        for i=1:n
            for j=i:n
                if A(i,j)~=0
                    c=num2str(A(i,j));                      % take A The weight in is converted into character               
                    text((x(i)+x(j))/2,(y(i)+y(j))/2,c,'Fontsize',10);  % Show the weight of the edge 
                    line([x(i) x(j)],[y(i) y(j)]);      % attachment 
                end
                text(x(i),y(i),num2str(i),'Fontsize',14,'color','r');   % Display the sequence number of the point             
                hold on;
            end
        end  
    end
    
end

   The above code is referenced from the following website ：

BFS Code
https://www.cnblogs.com/tiandsp/archive/2013/07/05/3174262.html
Matrix generates wireless network diagram （ To use ！）
https://www.cnblogs.com/tiandsp/archive/2012/12/26/2834654.html

summary

   For me personally , Width first search can better help me understand the characteristics of this algorithm ： Looking for nodes layer by layer from the inside out . You can remember according to your own understanding characteristics . The above is the main content of this paper , I hope you can get something ~