Depth-First Search (DFS)

1. Introduction: The Maze Explorer

If BFS is a ripple in a pond expanding equally in all directions, DFS is a person trying to navigate a maze by keeping their hand on the right wall. They walk down a single path as far as possible, taking every right turn they see. When they hit a dead end, they backtrack to the last intersection and try the next path.

Depth-First Search is arguably the most versatile algorithm in computer science. While it cannot guarantee the shortest path, its recursive nature makes it the absolute best choice for tasks that require exploring every possible state: detecting cycles, finding connected components, parsing dependencies, and solving combinatorial puzzles (Backtracking).

2. Core Concept: The Call Stack and Recursion

DFS explores aggressively deep. When it visits a node A, and sees neighbors B and C, it visits B. If B has a neighbor D, it visits D immediately! It doesn't look at C until the entire branch stemming from B has been exhausted.

Because we need to "remember" to come back and visit C, DFS implicitly uses a Stack data structure. While you can write DFS iteratively using a java.util.Stack, 99% of developers write DFS recursively, utilizing the operating system's internal Call Stack to manage the backtracking automatically.

3. Beginner Code Example: Connected Components

Problem Statement: (LeetCode 323) Number of Connected Components in an Undirected Graph. Given n nodes and an array of edges, return the number of isolated "islands" of connected nodes.

The Insight: If we run DFS from a node, it will mark every single node in its entire component as visited. If we iterate through all n nodes, and find one that isn't visited, it means we have discovered a brand new disconnected island!

import java.util.ArrayList;
import java.util.List;

public class ConnectedComponents {
    public int countComponents(int n, int[][] edges) {
        // 1. Build Adjacency List
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < n; i++) adj.add(new ArrayList<>());
        for (int[] edge : edges) {
            adj.get(edge[0]).add(edge[1]);
            adj.get(edge[1]).add(edge[0]);
        }
        
        boolean[] visited = new boolean[n];
        int components = 0;
        
        // 2. Loop through all nodes
        for (int i = 0; i < n; i++) {
            if (!visited[i]) {
                components++; // Found a new island!
                dfs(i, adj, visited); // Sink the entire island
            }
        }
        
        return components;
    }
    
    private void dfs(int node, List<List<Integer>> adj, boolean[] visited) {
        // Base case / Cycle prevention
        if (visited[node]) return;
        
        visited[node] = true;
        
        // Explore all neighbors
        for (int neighbor : adj.get(node)) {
            dfs(neighbor, adj, visited);
        }
    }
}

Complexity Analysis:

• Time Complexity: $O(V + E)$. We check every node and traverse every edge exactly twice (once from each direction).
• Space Complexity: $O(V + E)$ for the adjacency list, and $O(V)$ for the recursion call stack in the worst case (a completely straight line graph).

4. Intermediate Code Example: Cycle Detection in a Directed Graph

Problem Statement: (LeetCode 207) Course Schedule. There are a total of numCourses courses you have to take. Some courses have prerequisites (e.g., [0, 1] means to take course 0 you have to first take course 1). Return true if you can finish all courses. Otherwise, return false.

The Insight: If a curriculum has a cycle (A requires B, B requires C, C requires A), it is impossible to complete. This is a Directed Graph Cycle Detection problem. In a directed graph, a simple visited array isn't enough. We need to distinguish between nodes we are currently visiting in our active DFS path, and nodes we have fully finished visiting. We do this using a 3-state visited array:

• 0 = Unvisited
• 1 = Visiting (Currently on the recursive stack)
• 2 = Visited (Fully processed and safe)

If our DFS ever hits a node marked 1, we have walked back in on ourselves. A cycle exists!

import java.util.ArrayList;
import java.util.List;

public class CourseSchedule {
    public boolean canFinish(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]); // pre[1] must be taken before pre[0]
        }
        
        int[] state = new int[numCourses];
        
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0) {
                if (hasCycle(i, adj, state)) return false;
            }
        }
        return true; // No cycles found
    }
    
    private boolean hasCycle(int node, List<List<Integer>> adj, int[] state) {
        if (state[node] == 1) return true;  // Hit a node in our current path (CYCLE!)
        if (state[node] == 2) return false; // Hit a previously verified safe node
        
        state[node] = 1; // Mark as currently visiting
        
        for (int neighbor : adj.get(node)) {
            if (hasCycle(neighbor, adj, state)) return true;
        }
        
        state[node] = 2; // Finished processing, mark as safe
        return false;
    }
}

5. Advanced Code Example: Topological Sort

If a Directed Acyclic Graph (DAG) represents dependencies (like a build system where Library A must compile before Library B), what is the correct order to process the nodes? This ordering is called a Topological Sort.

The Insight: We can use DFS! If we do a standard DFS, a node only finishes its execution (hits the bottom of the function) after all of its descendants have been fully processed. Therefore, if we push a node onto a Stack right before the DFS function returns, the Stack will contain a perfectly valid Topological Sort (from top to bottom).

import java.util.ArrayList;
import java.util.List;
import java.util.Stack;

public class TopologicalSort {
    public int[] findOrder(int numCourses, int[][] prerequisites) {
        List<List<Integer>> adj = new ArrayList<>();
        for (int i = 0; i < numCourses; i++) adj.add(new ArrayList<>());
        for (int[] pre : prerequisites) {
            adj.get(pre[1]).add(pre[0]);
        }
        
        int[] state = new int[numCourses];
        Stack<Integer> stack = new Stack<>();
        
        for (int i = 0; i < numCourses; i++) {
            if (state[i] == 0) {
                // If a cycle exists, Topological Sort is mathematically impossible
                if (dfs(i, adj, state, stack)) return new int[0]; 
            }
        }
        
        int[] order = new int[numCourses];
        int i = 0;
        while (!stack.isEmpty()) {
            order[i++] = stack.pop();
        }
        return order;
    }
    
    private boolean dfs(int node, List<List<Integer>> adj, int[] state, Stack<Integer> stack) {
        if (state[node] == 1) return true;
        if (state[node] == 2) return false;
        
        state[node] = 1;
        for (int neighbor : adj.get(node)) {
            if (dfs(neighbor, adj, state, stack)) return true;
        }
        state[node] = 2;
        
        // POST-ORDER ACTION: Push to stack after all dependencies are processed
        stack.push(node);
        return false;
    }
}

6. Common Mistakes Beginners Make

1. Not passing the visited array correctly

   • The Mistake: Re-initializing the visited array inside the for loop before calling DFS.
   • Why it's wrong: The visited array must be global to the entire graph traversal to remember which nodes have been seen across different component islands.

2. Confusing Undirected and Directed Cycle Detection

   • The Mistake: Using a boolean[] visited array and returning true if you see a visited node in a Directed Graph.
   • Why it's wrong: In a Directed Graph, A -> B and C -> B is perfectly valid. If DFS goes A -> B (marking B as visited), and then starts a new DFS from C, hitting B again does NOT mean there is a cycle! It just means two paths merged. This is why Directed Graphs require the 3-state Visiting vs Visited logic.

3. StackOverflow on massive graphs

   • The Mistake: Trusting recursion for $N = 100,000$.
   • Why it's wrong: Java's default call stack limit is around 10,000 frames. Deep recursion will crash. For massive production graphs, you must manually rewrite the DFS using an iterative java.util.Stack.

7. Interview Q&A

Q1: How do you detect a cycle in an UNDIRECTED graph? Answer: We just use a standard boolean[] visited array. However, we must pass a parent parameter in our DFS. If we visit a neighbor that is already visited, AND that neighbor is NOT our immediate parent, then we have found a cycle!

Q2: What is Kahn's Algorithm? Answer: It is an iterative alternative to DFS for Topological Sorting. It uses a Queue and tracks the "In-Degree" (number of incoming edges) of every node. Nodes with In-Degree 0 have no prerequisites and are added to the queue. As they are processed, their neighbors' In-Degrees are decremented. It's heavily preferred if the interviewer asks you to return the Lexicographically smallest topological sort (by swapping the Queue for a PriorityQueue).

Q3: Can DFS be used to find the shortest path? Answer: No! DFS finds a path, usually the longest one first. Only BFS guarantees the shortest path in an unweighted graph. (The exception is a Tree, where there is exactly one path between any two nodes anyway).

8. Practice Problems

1. Number of Islands (LeetCode 200)
   • Goal: Master DFS on a 2D Matrix (finding connected components).
2. Course Schedule (LeetCode 207)
   • Goal: Master Directed Graph Cycle Detection using 3 states.
3. Course Schedule II (LeetCode 210)
   • Goal: Add a Stack to return the Topological Sort order.

9. Summary

• The Use Case: Exploring all states, cycle detection, topological sorting, and parsing matrices.
• The Core Setup: A recursive function utilizing a visited array.
• Undirected Cycle Detection: Check if neighbor is visited && neighbor != parent.
• Directed Cycle Detection: Use an int[] state array (0=Unvisited, 1=Visiting, 2=Visited).
• Topological Sort: A Post-Order DFS. Push the node to a Stack right before the function returns.