Skip to content

Depth first traversal

Introduction

The depth-first search algorithm (English: Depth-First-Search, DFS) is an algorithm for traversing or searching trees or graphs. Traverse the nodes of the tree along the depth of the tree and search the branches of the tree as deep as possible. When the edges of node v have been explored, the search will backtrack to the starting node of the edge where node v is found. This process continues until all nodes reachable from the source node have been found. If there are still undiscovered nodes, select one of them as the source node and repeat the above process. The whole process is repeated until all nodes are visited. It is a blind search.

Depth-first search is a classic algorithm in graph theory. The depth-first search algorithm can generate the corresponding topological sorting table of the target graph, and the topological sorting table can conveniently solve many related graph theory problems, such as the maximum path problem.

For inventing the "depth-first search algorithm", John Hopcroft and Robert Tayan jointly won the highest award in the computer field in 1986: the Turing Award.

As of now (2020-02-21), there are 129 questions in LeetCode for depth-first traversal. The question types in LeetCode are definitely super big. For the tree problem, we can basically use DFS to solve it, and we can even do breadth-first traversal based on DFS. It does not necessarily mean that DFS cannot do BFS (breadth first traversal) things. And since DFS can usually be done based on recursion, the algorithm will be more concise. In occasions where performance is highly inviting, I suggest you use iteration. Otherwise, try to use recursion. Not only is it simple and fast to write, but it is also not easy to make mistakes.

In addition, depth-first traversal can be combined with retrospective topics. It is recommended to put these two topics together to learn.

The concept of DFS comes from graph theory, but there are still some differences between DFS in search and DFS in graph theory. DFS in search generally refers to violent enumeration through recursive functions.

Algorithm flow

  1. First put the root node into stack.
  2. Take the first node from stack and check if it is the target. If the target is found, the search ends and the result is returned. Otherwise, add one of its direct child nodes that have not been tested to stack.
  3. Repeat step 2.
  4. If there is no direct child node that has not been detected. Add the upper level node to stack. Repeat step 2.
  5. Repeat step 4.
  6. If stack is empty, it means that the whole picture has been checked-that is, there is no target to be searched in the picture. End the search and return "target not found".

The stack here can be understood as a self-implemented stack or a call stack

Algorithm template

const visited = {}
function dfs(i) {
 if (satisfy certain conditions) {
  // Return the result or exit the search space
 }

 visited[i] = true // mark the current state as searched
 for (according to the next state j that i can reach) {
  if (!visited[j]) {// If state j has not been searched
   dfs(j)
  }
 }
}

Topic recommendation

These are a few DFS topics that I have recently summarized, and will continue to be updated in the future~