[implementation of depth first search]

  The idea of depth first search ：

Starting from the initial node , Go to the adjacent node without passing through , Then the tag marks the node as having passed , Taking this node as the starting point , Find the adjacent nodes that have not passed again , When you find that there is no way to go （ The surrounding adjacent nodes have passed ） Then the original path returns to the previous node , See if there are any adjacent nodes that have not passed by , If there is one, go , If not, return to the previous node again and repeat the operation . Finally, the original path returns to the initial node , Then the search is completed .

summary ：

（1） Go deep , As long as there is an adjacent node that has not passed through

（2） When there is no way to go , Then the original path returns to the current node , See if there is a way to go , If there is one, go , If you don't, you'll go back the same way

（3） When the original path returns to the initial node , Description search ended . At the same time, it will find its way to go on the way back , When it's over , Is to ensure that all nodes go to （ Connected ）

Recursive implementation （ Pseudo code ）

void dfs(vertex v)
{
   visited[v]=true;
   while(v Adjacent nodes of i)
   {
       if( !visited[i])
          dfs(i);
    }
}
/*visited[n] Used to record whether the 

The details that the above code still needs to deal with are how to loop to all adjacent nodes . Different storage methods may lead to different

Time complexity ： Number of nodes N, Number of edges E

The main operations of depth first search are

1.visited[v]=true; Access once for each node

2. Every node v Adjacent nodes of i The interview of

matrix ：1 operation ：N Nodes N Time    2 operation ： For each current node, all nodes will be accessed , common N*N Time

O（N+N*N)=O(N*N)

Linked list ：1 operation ：N Nodes N Time    2 operation ： Each current node accesses its own neighboring nodes , common 2*E Time

O(N+2*E)=O(N+E)