Depth First Search (DFS) for Graphs

# CHAPTER 22

Depth First Search (DFS) for Graphs #

1. Introduction #

2. Learning Objectives #

• Trace the backtracking recursive matrix of a Graph DFS.

• Understand how DFS maps deep topological networks (like Maze generation).

• Implement a dual-cache system (Visited + RecursionStack) for Cycle Detection.

• Write a production-ready Cycle Detection algorithm in Python/Java.

3. The DFS Spear (Plunging and Backtracking) #

The Logic: When DFS hits Node A, it finds A's neighbors: B, C, D. Instead of putting them all in a line (like BFS), DFS says: "I am going to grab B and see how far down the rabbit hole B goes. I will completely ignore C and D until I fully map the entire sub-universe connected to B!" This aggressive plunging is what allows DFS to rapidly strike the absolute bottom of a graph matrix.

4. Application: Cycle Detection in Directed Graphs #

The Dual-Cache Solution: We need TWO Arrays (or Hash Sets):

1. 1. Visited: Tracks nodes we have fully mapped and cleared forever.

1. 2. RecursionStack: Tracks nodes that are currently active in the present plunging downward line.

The Golden Rule of Cycles: If your plunging DFS hits a neighbor that is ALREADY flagged as True in the RecursionStack (meaning the node is actively being evaluated right now in the current chain), you have mathematically proven the path circled backward upon itself. Cycle Detected!

5. Code Execution: Cycle Detection (Python) #

def is_cyclic(graph, v, visited, rec_stack):
    # Mark the current node as visited and add to current active path stack
    visited.add(v)
    rec_stack.add(v)
    
    # Plunge into all directed neighbors
    for neighbor in graph.get(v, []):
        # Scenario 1: Unvisited neighbor. Plunge DFS!
        if neighbor not in visited:
            if is_cyclic(graph, neighbor, visited, rec_stack):
                return True # Loop found deep down, bubble up the error!
                
        # Scenario 2: Neighbor is ALREADY in the active path stack! BOOM!
        elif neighbor in rec_stack:
            return True # Cycle Detected!
            
    # As the recursion unwinds/backtracks, REMOVE node from active path stack!
    rec_stack.remove(v)
    return False

# Directed Graph
graph = {
    'A': ['B', 'C'],
    'B': ['D'],
    'C': ['Z'],
    'D': ['A'], # FATAL LOOP: D points back to A!
    'Z': []
}

visited = set()
rec_stack = set()

# Wrapping in Master loop for disconnected islands
has_cycle = False
for node in graph:
    if node not in visited:
        if is_cyclic(graph, node, visited, rec_stack):
            has_cycle = True
            break

print(f"Contains Cycle? {has_cycle}") # Output: True

6. Applications of Graph DFS #

• Maze Generation and Solving: DFS naturally burrows deep paths, making it the algorithm of choice for generating video game mazes.

• Topological Sorting: Used to order tasks based on prerequisites (covered in Chapter 26).

• Strongly Connected Components (Kosaraju's Algorithm): DFS is used to identify tightly clustered groups in massive networks.

7. Complexity Analysis #

• Time Complexity: $O(V + E)$. It visits every vertex once and evaluates every edge.

• Space Complexity: $O(V)$. The OS Call stack drops as deep as the longest path in the graph, which in worst-case (a linear graph) is $V$. The Visited and RecursionStack caches also require $V$ space.

8. Common Mistakes #

• Forgetting to pop from the RecursionStack: In the cycle detection code, when a node finishes evaluating all its neighbors and is ready to return (backtrack), you MUST execute rec_stack.remove(v). If you forget this, the node stays flagged as "active" permanently, causing massive false-positive cycle alarms on subsequent DFS plunges!

9. Exercises #

1. 1. Trace the Visited and RecursionStack array states step-by-step for the A -> B -> D -> A cycle in the Section 5 Python code.

1. 2. Why is finding a cycle in an *Undirected* Graph actually much easier, requiring only the standard Visited array and a Parent variable?

10. MCQs with Answers #

11. Interview Preparation #

• *System Dependencies:* "You are writing a task runner. Task A requires Task B. Task B requires Task C. How do you guarantee the software doesn't crash from circular dependencies?" *(Answer: Model the tasks as a Directed Graph where edges are requirements. Execute a DFS traversal utilizing an active RecursionStack tracking cache. If any node detects a neighbor actively flagged in the current stack, throw a Fatal Circular Dependency Error!)*

12. Summary #

13. Next Chapter Recommendation #