Depth-First Search (DFS)

# CHAPTER 24

Depth-First Search (DFS) #

1. Introduction #

Because of this aggressive plunging logic, DFS perfectly mirrors the native architecture of Recursion, allowing engineers to traverse massive matrices using practically zero lines of auxiliary code.

2. Learning Objectives #

• Explain the plunging, backtracking execution sequence of DFS.

• Contrast the Queue architecture of BFS with the Stack architecture of DFS.

• Implement DFS cleanly using OS Call Stack Recursion.

• Identify Cycle Detection algorithms using DFS.

3. The Execution Logic #

The Mechanics:

1. 1. Start at a Root Node (e.g., Node 0).

1. 2. Mark it Visited.

1. 3. Look at its neighbors. Pick the *very first* unvisited neighbor.

1. 4. Instantly halt Node 0! Recursively dive completely into that neighbor!

1. 5. Continue diving deeper and deeper.

1. 6. When a Node has zero unvisited neighbors remaining, the recursion naturally "unwinds" (Backtracks) up the Call Stack to a previous intersection to explore alternate paths.

4. Implementation in Code (Recursive) #

// Java Example: Recursive Depth-First Search
import java.util.*;

public class GraphDFS {
    
    // The Recursive Execution Engine
    public void executeDFS(int node, List<List<Integer>> adjList, boolean[] visited) {
        
        // 1. Instantly mark the current node as Visited
        visited[node] = true;
        System.out.print(node + " "); // Output the traversal path
        
        // 2. Iterate through all immediate neighbors
        for (int neighbor : adjList.get(node)) {
            
            // 3. If a neighbor is unvisited...
            if (!visited[neighbor]) {
                
                // 4. AGGRESSIVE DIVE! We halt the loop and plunge into the neighbor recursively!
                executeDFS(neighbor, adjList, visited);
                
                // The loop ONLY resumes after the entire deep branch is fully exhausted.
            }
        }
    }
}

5. DFS vs. BFS Comparison #

6. Cycle Detection using DFS #

7. Topological Sorting #

8. Real-World Applications #

1. 1. Maze Generation and Solving: DFS naturally mimics the human logic of walking a maze by keeping a hand on the right wall and backing up upon hitting dead ends.

1. 2. Path Dependency Verification: Compilers use DFS to verify that code modules do not circularly reference each other (e.g., File A imports File B, File B imports File A -> Crash).

1. 3. Deep Neural Networks: Traversing node weights structurally down the deep hidden layers of an AI matrix.

9. Common Mistakes #

• Stack Overflow Exception: DFS relies on OS Recursion. If you execute DFS on a massive graph that is essentially one giant straight line of 100,000 nodes, the recursion depth will reach 100,000 layers, violently shattering the OS Call Stack limit. In highly linear deep graphs, you MUST abandon recursion and write the DFS using a manual iterative while loop combined with a Stack object.

10. Exercises #

1. 1. Trace a DFS execution manually on a Binary Tree. Does the output perfectly match "Pre-Order Traversal"? Why?

1. 2. If a Graph has two entirely disconnected sections, how do you modify the code to ensure DFS visits every single node? *(Hint: Look at the overarching for loop).*

11. MCQs with Answers #

12. Interview Preparation #

• *Algorithmic Coding:* "Count the Number of Islands. Given a 2D grid matrix of 1s (land) and 0s (water), count the isolated islands." *(Answer: Iterate over the 2D array. The moment you find a 1, increment the island_count. Then, immediately launch an aggressive DFS that recursively spreads in all 4 directions (up, down, left, right), violently mutating every attached 1 into a 0 to sink the island so it's never double-counted!)*

13. Summary #

14. Next Chapter Recommendation #