Depth first search (DFS) and its matlab code

---

Preface

   Depth first search is a kind of graph algorithm , It can help users traverse all points , Next, let's study together ~

---

One 、 What is depth first search ？

   Depth-first algorithm , Full name $DepthFirstSearch$, Referred to as $DFS$. Its general idea is ： Start with a node , Random start walking , If it doesn't work , Save path ; Then step back , Until you can continue to walk randomly ; Finally finish all grid points , Then stop the program .
   Give an example ：

   This graph is an undirected graph , If we're from A Click to initiate a depth first search （ The following access order is not unique , The second point can be either B It can also be C,D）, Then we may get the following access process ：A->B->E（ There is no way ！ Go back to A)->C->F->H->G->D（ There is no way , Eventually back to A,A There are no adjacent nodes that have not been accessed , End of this search ）.
The above content is referenced from the following website ：

https://blog.csdn.net/weixin_42943114/article/details/104172146
https://baike.baidu.com/item/%E6%B7%B1%E5%BA%A6%E4%BC%98%E5%85%88%E6%90%9C%E7%B4%A2/5224976

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

1、 The basic idea of depth first search

   The method of depth first traversal graph is , From some vertex in the picture v set out ：
  （1） Visit vertex v;
  （2） Successively v Of the adjacent points that are not accessed , Depth first traversal of the graph ; Until the graph neutralizes v Vertices that have paths are all accessed ;
  （3） If there are still vertices in the graph that are not accessed , From a vertex that has not been visited , Do depth first traversal again , Until all the vertices in the graph have been visited .

2、 Algorithm idea and its application matlab Code

  （1） Mark all edges “ Not used ”, For any vertex v,k(v) = 0. Make i = 0,v = s.
  （2）i = i + 1,k(v) = i.
  （3） if v No, “ Not used ” Associated edge of , turn 5.
  （4） Choose one “ Not used ” Of and v Related sides e = vu, Mark e“ Used to ”. if k(u) != 0, turn 3; otherwise ,f(u) = v,v = u, turn 2.
  （5） if k(v) = 1, stop it .
  （6）v = f(v), turn 3.
   among , Above mentioned k(v) Called the vertex v Of DFS code ;f(v) Called the parent of the vertex ,v be called f(v) The son of , And in f(v) As the starting point 、v The directed edge at the end is called the parent-child edge .

%G Represents the adjacency matrix of a graph 
%W Represents the access order of the edges of the graph , Visit from small to large in order .
%K Represents the vertex label of the graph 
%f Represents the parent vertex of the corresponding vertex 

function [W k f] = DFS3(G)
n = size(G,1);
W = G;
v = 1;
k = zeros(1,n);
f = zeros(1,n);
b = sum(sum(W == 1));
c = sum(k == 0);
d = 1;
if b == 0 & c == 0 & v == 1
    d = 0;
end
k(1) = 1;
j = 2;
l = 2;

while d
    a = find(W(v,:) == 1);
    if isempty(a) & f(v) ~= 0
        W(v,f(v)) = l;
        l = l + 1;
        v = f(v);
    else
        for i = 1:length(a)
            if k(a(i)) == 0
                k(a(i)) = j;
                j = j + 1;
                W(v,a(i)) = l;
                l = l + 1;
                f(a(i)) = v;
                v = a(i);
                break;
            elseif k(a(i)) ~= 0
                W(v,a(i)) = l;
                l = l + 1;
            end
        end
    end
    b = sum(sum(W));
    c = sum(k == 0);
    if c == 0 & v == 1
        d = 0;
    end
end
W;

   The above content is referenced from the following website ：

https://blog.csdn.net/qq_43508527/article/details/89217460

summary

   That's all for today's study , I hope you can get something ~