Thought: For the newly discovered vertex V, if it has an unexplored edge starting from that edge, explore along that edge. If all edges of V have been explored, go back to the edges where V was found to have a starting point. Until all vertices reachable from the source origin have been explored. If there are any unexplored vertices, define it as a new source vertex and continue the process.

Try every possible outcome, like a maze, and if you don’t get it, go back to where you came from and keep exploring

Explore the entire diagram

DFS(V,Adj):
    parent={}
    for s inV: // Iterate over all the points in the graphif s not inParent [s]=None // The source does not set dfs-visit (Adj,s) // Explore all points that the current source vertex can reachCopy the code

Given a source vertex s,DFS implementation

DFS-Visit(Adj,s):
   for v inAdj[s]: // Iterate over all edgesif v not inParent: // The current edge is not traversed parent[v]=s // The record is traversed dfS-visit (adj,v)Copy the code

Taking a directed graph as an example, suppose that all vertices are traversed in alphabetical order, i.e. V=[A,b, C, D,e,f], the original graph

  1. The first step is to explore the edges from A to B, and find that B has more edges. Keep going down until D, where d has no downward edges. The first DFS-visit execution ends

  1. There is no new edge that has not been explored. Finally, DFS exploration generates two depth-first trees

Depth-first trees refer to trees generated by DFS, resulting in the two parts indicated by the orange arrow in 3

Time complexity

O(V+E); Its traversal rule still requires that all nodes be traversed once, for each change, only those that have not been traversed are traversed once

What is the use of depth-first search?

1. The classification

  • From the tree. If vertex V is first discovered on the search edge (u,v), then (u,v) is the tree edge, as shown in figure (a,b).
  • The positive side. Some non-tree edge from u to V, like (a,d), where a to D has edges, but it doesn’t go into the tree
  • The reverse side. The edge that connects u to its ancestor vertex V, as in (d,b).
  • Cross border. The resulting tree does not have a parent-child relationship between two vertices. So let’s say that this is g,d.

In the algorithm, the tree edge judgment can be seen through parent, and the reverse of parent is the tree edge, which can be identified.

If the next vertex is in the stack, then this edge is the opposite edge.

How do I tell if there are rings in a graph?

Graph G has a ring if and only if there is an antiedge in the graph. The proof is as follows:

  • If there is a ring, there is an antiedge. Let’s say I pick a point from the ring, as the first vertex of DFS traversal, prove (.) is the opposite side: it is known that,Before the visit,Must have been finished,Before the visit,Must have been accessed, when accessedNext checkThe time,Already in the stack, then (.) is the reverse side

  • If there is an antiedge, there is a ring. First, s to T must be on the edge of the tree, and then t to S is an antiedge, so it must be a ring

2. The Job scheduling

The Job itself is an acyclic digraph, and there must be a certain order between vertices. The last one can only be executed after the first one is finished

It uses an algorithm called topological sort. Topological sort uses DFS internally, and the output is the reverse order of the vertices when parent is done.

The result of this ordering is that, assuming all vertices in the graph are on the same level, all directions are from left to right

prove

We just need to prove that, for any edge, e=(u,v), u doesn’t finish until v finishes

  • The access to U occurs before v: since u and V have an edge,v must be accessed before U is completed, and u cannot be completed until V is completed
  • V is accessed before u: since there is an edge between u and v, if V is accessed first, if there is a path from V to U, then there will be a loop, so u will not be executed at all, that is, v will be executed first

The appendix

Introduction to Algorithms (MIT 6.006 Lecture 14)