Exploring Graphs with DFS

1. The Core Idea: Going Deep

While BFS uses a queue to explore layer by layer (like ripples in a pond), DFS uses a stack to go deep. Imagine you're in a maze. Instead of checking every path of length 1, then every path of length 2, you'd pick one path and follow it until you hit a dead end. Only then would you backtrack to your last turn and try a different route. This is the essence of DFS.

To implement this "last-in, first-out" exploration strategy, DFS relies on a stack. This can be the program's own function call stack (in a recursive implementation) or an explicit stack data structure (in an iterative one).

To get a clear visual of how DFS works and differs from BFS, and to understand the critical role of a visited set, please watch the following video segment.

2. Recursive DFS: The Intuitive Approach

For many developers, the recursive implementation of DFS is the most natural. The function call stack elegantly handles the backtracking for us.

The logic is straightforward:

1. From a given node, mark it as visited.
2. Then, for each of its unvisited neighbors, recursively call the function on that neighbor.
3. The recursion naturally "backtracks" when a path is fully explored (i.e., it hits a node with no unvisited neighbors).

Here is a standard template for a recursive DFS. This structure is a great starting point for many interview problems.

# graph is an adjacency list, e.g., {'A': ['B', 'C'], ...}
# node is the starting node
# visited is a set to keep track of visited nodes

def dfs_recursive(graph, node, visited):
    if node in visited:
        return

    visited.add(node)
    print(f"Visiting {node}") # Process the node

    for neighbor in graph.get(node, []):
        if neighbor not in visited:
            dfs_recursive(graph, neighbor, visited)

# --- Driver Code ---
# graph = ...
# visited = set()
# dfs_recursive(graph, 'A', visited)

This simple traversal is the foundation. Now, let's see the iterative version.

3. Iterative DFS: The Explicit Stack

While recursion is elegant, it can lead to a "maximum recursion depth exceeded" error on very large or deep graphs. An iterative approach using an explicit stack avoids this and gives you more control.

The logic mirrors the stack-based visualization you saw in the video:

1. Initialize a stack and push the starting node onto it.
2. Initialize a visited set.
3. While the stack is not empty, pop a node.
4. If the node has already been visited, skip it.
5. Mark the node as visited and process it.
6. Push all its unvisited neighbors onto the stack.

This code snippet from the "Master Graph Algorithms" article provides a clean iterative implementation.

4. Application: Path Finding with DFS

DFS is excellent for path-related problems. As your interview prep guide from InterviewCrunch notes, these can be split into "validation" problems (does a path exist?) and "path" problems (what is the path?).

Let's summarize these patterns.

Pattern 1: Path Validation

To check if a path exists between start and target, we modify our recursive DFS to return a boolean.

• If curr == target, we've found it, so we return True.
• The recursive call becomes: if any of my neighbors can find the target (if dfs(...)), return True.
• If the loop finishes without finding the target, return False.

Here is the pattern from the article, adapted slightly for clarity:

def dfs_path_exists(curr, target, graph, visited):
    if curr in visited:
        return False
    visited.add(curr)
    
    if curr == target:
        return True
        
    for neighbor in graph.get(curr, []):
        if dfs_path_exists(neighbor, target, graph, visited):
            return True # Path found through this neighbor!
            
    return False # No path from this node

Pattern 2: Reconstructing the Path

This is a powerful pattern that previews the backtracking technique we'll cover later. The key is to pass a list representing the current path down the recursion.

1. Append the current node to the path.
2. If the current node is the target, you've found a path. Return True.
3. Recursively call on neighbors. If any call returns True, it means a path was found, so propagate True up the call stack.
4. If a recursive call returns False, it means that neighbor led to a dead end. You must backtrack by popping the node from the path before trying the next neighbor.

This "add, explore, remove" pattern is fundamental. The InterviewCrunch article provides a great template for this.

5. Complexity and When to Use DFS vs. BFS

• Time Complexity: $O(V+E)$

  • Just like BFS, DFS visits every vertex ($V$) and every edge ($E$) once in the worst case.

• Space Complexity: $O(V)$

  • For recursive DFS, the space is determined by the maximum depth of the recursion call stack. In the worst case (a long, chain-like graph), this can be $O(V)$.
  • For iterative DFS, the space is the maximum size of the explicit stack, which can also be $O(V)$ in the worst case.

DFS vs. BFS - A Quick Guide for Interviews

Conclusion

You have now added the second major graph traversal algorithm to your toolkit. DFS is not just for traversal; it's the conceptual foundation for many advanced algorithms like topological sorting, cycle detection, and the entire backtracking paradigm.

Key Takeaways:

• DFS explores deeply, following one path to its conclusion before backtracking.
• It is powered by a stack, either the implicit function call stack (recursive) or an explicit one (iterative).
• A visited set is crucial to handle cycles and avoid redundant work.
• DFS can be adapted to solve path validation (does a path exist?) and path reconstruction problems.
• The time complexity is $O(V+E)$, and space complexity is $O(V)$, related to the maximum path depth.

Preview of the Next Lesson:

In our next lesson, we will apply these traversal techniques to a very common interview pattern: grid-based graph problems. We'll tackle classics like "Number of Islands," where you'll see how to model a 2D grid as a graph and use DFS or BFS to find and count distinct groups of connected cells.