The world’s leading publication for data science, AI, and ML professionals.

Top Coding Algorithms – Depth First Search

All coding problems that can be formatted into tree structures are very likely be solved by either breadth first search or depth first…

All coding problems that can be formatted into tree structures are very likely to be solved by either breadth first search or depth first search. Different from breadth first search that is implemented using stack, depth first search takes a divide and conquer approach, which is implemented using recursion.

Pseudo Code

Input: A graph G and a vertex v of G

Output: All vertices reachable from v labeled as discovered

procedure DFS(G, v) is
    label v as discovered
    for all edges from v to w that are in G.adjacentEdges(v) do
        if vertex w is not labeled as discovered then
            recursively call DFS(G, w)
(from wiki)

(Notice that only when vertex w is not visited before do we proceed, this avoids cycle in the graph or tree)

The reason one can use recursion to solve a problem is that one big problem can be divided into multiple subproblems and each subproblem follow the same logic and structure. For example, here if we want to find the path from point A to point B in a tree structure, you can summarise the process as a repetitive formula:

path = current_path + DFS(sub_tree)

Example

Consider the following problem,

Find all the paths from point 0 to point 6.

Notice that there is a cycle (double arrow) in the graph (1 and 4).

The node connections are stored in a dictionary. The recursion stops when either it reaches the end point or leaf node.

Which gives the result:

find solution path [0, 1, 4, 6]
find solution path [0, 2, 5, 6]
find solution path [0, 2, 5, 4, 6]

Variations

Consider the following problem:

Given a n-ary tree, find its maximum depth.
The maximum depth is the number of nodes along the longest path from the root node down to the farthest leaf node.
Input: root = [1,null,3,2,4,null,5,6]
Output: 3

To divide the problem into subproblems, it follows the formula

max_depth = 1 + max(max_depth(child_1), max_depth(child_2), ...)

Solution

(checkout code here)


Related Articles