This is the 8th day of my participation in the November Gwen Challenge. Check out the event details: The last Gwen Challenge 2021

According to this binary tree, let’s manually simulate the depth-first traversal algorithm. We visit A first, and A visits B. After B visits, we visit C. When C visits c and finds that C has no children, we go back to B and visit E. Found e children have access to over again back to point b detection point b children have access Are back to point a and then access point such access + c retraction last order of this tree is: abdehcfg in the process, there will be a (inside) recursive thought if our first order of tree traversal, traverse the result: abdehcfg

Therefore, the idea is sorted out again according to the process simulated above: first, an initial vertex V is visited, then any unvisited adjacency w1 of V is visited, and then any unvisited adjacency w2 of W1 is visited.. We keep going down, and when we can’t go any further down, we go back to the most recently visited vertex, and if there’s any adjacency left on that vertex, we continue until all the nodes have been accessed

Take a look at his code implementation with the above ideas in mind:

bool visited[MaxNum]; Void DFSTraverse(Graph G){for(int I =0; i<G.vexnum; I ++){// Initialize the array visited[I] = false; } for(int i; i<G.vexnum; i++){ if(visited[i]){ DFS(G,i); } } } void DFS(Graph G,int v){ visit(v); visited[v] = true; For (w=FirstNeighbor(G,v); W>=0; NextNeighbor(G,v,w) {if(! visited[w]){ DFS(G,w); }}}Copy the code

Algorithm performance analysis:

Time complexity:

Adjacency matrix: O (| V | 2)

Adjacency list: O (+ | E | | V |)

Space complexity: O (| V |) (need to work a recursive stack)

  • conclusion

The graph traversal algorithm, the breadth-first traversal algorithm and depth-first traversal algorithm shared yesterday and today, breadth-first traversal is assisted by the first-in, first-out characteristics of queues, and depth-first is assisted by a recursive stack

Which two times calendar calculation method can be used to test pattern connectivity, for undirected graph, starting from any node, traversal can visit all nodes at a time, so can’t finish a visit all nodes is known, the picture is a connected graph for directed graph, from the initial point to each point path, is to be able to access all the nodes On the other hand will not be able to access. Therefore, for an undirected graph, the number of times of calling BFS(G, I) and DFS(G, I) is the number of connected components of the graph, while for a directed graph, a non-strongly connected graph cannot access all nodes.