Depth First Search (Graph Theory)

The full name of DFS is Depth First Search, and its Chinese name is Depth First Search. It is an algorithm for traversing or searching trees or graphs. The so-called depth first means trying to go to deeper nodes every time.

This algorithm is often explained alongside BFS, but apart from being able to traverse connected blocks of graphs, both have completely different purposes. There are very few situations where the two algorithms can be mixed.

DFS is also used to refer to searches implemented using recursive functions, but in fact the two are not the same. Please refer to DFS (Search).

The most significant feature of DFS is that it calls itself recursively. At the same time, similar to BFS, DFS will mark the visited points and skip the marked points when traversing the graph to ensure that each point is only visited once. Functions that comply with the above two rules are DFS in a broad sense.

Specifically, the general structure of DFS is as follows:

DFS(v) // v can be a vertex in the graph, or an abstract concept, such as dp state, etc.

   Mark access on v

   for u in v adjacent nodes

     if u has not been marked as accessed then

       DFS(u)

     end

   end

end