Understanding depth-first search pattern

The depth-first search algorithm starts from a node and explores all the nodes in a branch before backtracking and choosing other paths. It makes arbitrary choices of nodes at each depth until it can no longer make a choice and backtracks to update previous choices. It is a recursive algorithm that keeps track of all nodes in the path using a stack, enabling backtracking. The recursive implementation of the algorithm uses the function call stack to store nodes and any additional context at each step. Many graph problems can be efficiently solved using depth-first search.

The depth-first search algorithm

Let's examine the generic problem that can only be solved efficiently using depth-first search to better understand the pattern. Consider we have a graph, a source and destination node, a function f and a function g. We need to find the aggregated value of the function f over nodes in all the simple paths from the source node to the destination node. We need to further aggregate those aggregated values into a single value using the function g.

We can use depth-first search to solve the problem by exploring one path at a time, until it either reaches a dead end or the destination node. The recursive nature of the algorithm allows us to build a path on the fly and backtrack when necessary.

However, unlike depth-first traversal, which also uses depth-first search, we don't need a visited set to keep track of all previously visited nodes. We only need to keep track of nodes in the currently explored path, because if we ever reach a previously visited node not in the current path, the resulting path must still be explored, as it will be counted as a unique path to the destination node.