Depth-First Search on Graphs

The Intuition: Navigating a Labyrinth

Imagine you're trying to find your way through a complex maze. One natural strategy is to pick a path and follow it as far as you can. When you hit a dead end, you turn around, walk back to the last intersection where you had a choice, and try a different, unexplored path. You repeat this process until you've explored all possible routes from that intersection, at which point you backtrack even further.

This is precisely the intuition behind Depth-First Search. It starts at a source node and explores as far as possible along each branch before backtracking.

The video below provides an excellent "explorer" analogy that visually builds this intuition.

The core principle of DFS is this aggressive, "depth-first" exploration. Unlike BFS, which guarantees finding the shortest path in terms of edges, DFS does not. Instead, it produces a path that is long and deep, which can be very useful for other types of problems.

The Recursive Approach: The Natural Way to Go Deep

The "go deep and backtrack" nature of DFS makes it a perfect fit for a recursive algorithm. The logic is elegant:

1. Start at a node u. Mark it as visited.
2. For each neighbor v of u:
3. If v has not been visited, recursively call DFS on v.
4. Once all neighbors have been visited, the function for u returns, effectively "backtracking" to the node that called it.

To prevent infinite loops in graphs with cycles, we use a visited set or array, just as we did with BFS.

The following image visualizes this recursive process, showing the Python code alongside the graph and the state of the recursive call stack.

To see this logic explained with a step-by-step animation, let's return to the Reducible video. It does an excellent job of showing how the call stack manages the backtracking process automatically.

The Iterative Approach: Swapping the Queue for a Stack

In our last lesson, we saw that BFS uses a queue (First-In, First-Out) to manage its "to-visit" list, resulting in a level-by-level traversal. To implement DFS iteratively, we simply swap the queue for a stack (Last-In, First-Out). This single change is what transforms the search from broad to deep.

Here's the iterative algorithm:

1. Initialize: Create an empty stack and a visited set. Push the starting node onto the stack.
2. Loop: While the stack is not empty:
   a. Pop: Remove the node from the top of the stack. Let's call this current_node.
   b. Check and Process: If current_node has not been visited:
   i. Mark it as visited.
   ii. Process it (e.g., print its value).
   iii. Explore Neighbors: For each neighbor of current_node, if the neighbor has not been visited, push it onto the stack.
3. Terminate: Once the stack is empty, all reachable nodes have been visited.

By always taking the most recently added node from the stack, the algorithm continuously dives deeper into the graph.

The image below shows a snapshot of an iterative DFS, highlighting the state of the stack.

The following video segment demonstrates this iterative process, explicitly showing how the stack's LIFO behavior drives the deep exploration.

Since you're focused on practical implementation, here's a concise Python implementation for both the recursive and iterative versions.

Pre-Order vs. Post-Order Traversal

A quick but important distinction in DFS is the order in which we "process" a node.

• Pre-order: We process the node before visiting its neighbors. This is what we have done in all examples so far (e.g., printing the node as soon as we encounter it).
• Post-order: We process the node after we have visited all of its descendants. In a recursive implementation, this simply means moving the "process" step to after the loop that makes the recursive calls.

This distinction is crucial for algorithms like topological sorting. The Reducible video offers a quick explanation of this concept.

Complexity

Just like BFS, the performance of DFS is highly efficient. For a graph with $V$ vertices and $E$ edges represented by an adjacency list:

• Time Complexity: $O(V+E)$. Each vertex is visited once, and each edge is traversed once (or twice in an undirected graph).
• Space Complexity: $O(V)$. In the iterative version, the stack can hold up to $V$ vertices in the worst case (a long, chain-like graph). In the recursive version, the space is determined by the maximum depth of the recursion, which can also be $O(V)$.

Conclusion

In this lesson, we plunged into the world of Depth-First Search, contrasting its "deep" exploration strategy with the "broad" approach of BFS. You've seen how this powerful traversal algorithm can be implemented both elegantly with recursion and explicitly with a stack.

Here are the key takeaways:

• DFS explores as deeply as possible down one path before backtracking.
• It is naturally implemented using recursion, where the call stack manages the backtracking.
• The iterative version uses a stack (LIFO) to mimic the recursive behavior.
• The time complexity is $O(V+E)$, the same as BFS, making it very efficient.
• Small implementation changes can produce different traversal orders, such as pre-order and post-order.

In our next lesson, we will put both BFS and DFS to work. We will use them to solve a common and practical problem: finding all connected components in a graph. This will be your first step in using these traversal algorithms as building blocks for more complex analysis.