Graph DFS

Intuition

Picture exploring a cave system with a ball of string. At every junction you pick an unexplored tunnel and keep going until you hit a dead end or a chamber you have already marked. Then you follow the string back to the last junction that still has an unexplored tunnel. That is depth-first search (DFS): commit to a direction, go deep, and backtrack only when forced.

What makes DFS powerful is not the order it visits nodes but the timing. Each node has a moment when DFS first enters it (pre-order) and a moment when DFS finishes all of its descendants and leaves it (post-order). Those two timestamps answer questions BFS cannot answer cheaply: does this directed graph contain a cycle, and in what order can its tasks be scheduled?

How it works step by step

1. Give every node one of three colours: white (never seen), gray (entered, still on the current path) and black (fully finished).
2. Call dfs(u) on a white node. Paint it gray and record it in the pre-order list.
3. For each neighbor v of u: if v is white, recurse into it. If v is gray, you have found a back edge, which means a cycle in a directed graph. If v is black, skip it.
4. When every neighbor is handled, paint u black and append it to the post-order list.
5. Repeat from every node that is still white so disconnected parts are covered. Each fresh start in an undirected graph is a new connected component.
6. For a DAG, reverse the post-order list to get a valid topological order.

Dry run on a small DAG

Directed edges 0→1, 0→2, 1→3, 2→3, 3→4. We start DFS at 0 and visit neighbors in list order. The stack column is the recursion stack after the action.

Reversing the post-order gives 0, 2, 1, 3, 4, and every edge points forward in that list. If there were an edge 4→1, step 5 would find 1 still gray, which is a back edge and proof of the cycle 1→3→4→1.

Code

import java.util.*;

public class GraphDFS {
    private static final int WHITE = 0, GRAY = 1, BLACK = 2;

    // Recursive DFS. Returns a topological order, or null if the graph has a cycle.
    public static List<Integer> topoSort(List<List<Integer>> adj) {
        int n = adj.size();
        int[] color = new int[n];
        List<Integer> post = new ArrayList<>();
        for (int u = 0; u < n; u++) {
            if (color[u] == WHITE && !visit(u, adj, color, post)) return null;
        }
        Collections.reverse(post);
        return post;
    }

    private static boolean visit(int u, List<List<Integer>> adj, int[] color, List<Integer> post) {
        color[u] = GRAY;
        for (int v : adj.get(u)) {
            if (color[v] == GRAY) return false;              // back edge: cycle
            if (color[v] == WHITE && !visit(v, adj, color, post)) return false;
        }
        color[u] = BLACK;
        post.add(u);                                         // post-order position
        return true;
    }

    // Undirected graph: count components with an explicit stack (no recursion).
    public static int countComponents(List<List<Integer>> adj) {
        boolean[] seen = new boolean[adj.size()];
        int components = 0;
        for (int s = 0; s < adj.size(); s++) {
            if (seen[s]) continue;
            components++;
            Deque<Integer> stack = new ArrayDeque<>();
            stack.push(s);
            seen[s] = true;
            while (!stack.isEmpty()) {
                int u = stack.pop();
                for (int v : adj.get(u)) {
                    if (!seen[v]) { seen[v] = true; stack.push(v); }
                }
            }
        }
        return components;
    }
}

def topo_sort(n, edges):
    """Iterative three-colour DFS. Returns a topological order or None on a cycle."""
    adj = [[] for _ in range(n)]
    for u, v in edges:
        adj[u].append(v)

    WHITE, GRAY, BLACK = 0, 1, 2
    color = [WHITE] * n
    post = []
    for start in range(n):
        if color[start] != WHITE:
            continue
        color[start] = GRAY
        stack = [(start, iter(adj[start]))]      # node plus where we are in its list
        while stack:
            node, neighbors = stack[-1]
            nxt = next(neighbors, None)
            if nxt is None:                      # all children done: post-order
                color[node] = BLACK
                post.append(node)
                stack.pop()
            elif color[nxt] == GRAY:
                return None                      # back edge
            elif color[nxt] == WHITE:
                color[nxt] = GRAY
                stack.append((nxt, iter(adj[nxt])))
    return post[::-1]


print(topo_sort(5, [(0, 1), (0, 2), (1, 3), (2, 3), (3, 4)]))  # [0, 2, 1, 3, 4]
print(topo_sort(3, [(0, 1), (1, 2), (2, 0)]))                  # None

The Python version keeps an iterator per stack frame, which is how you get true post-order without recursion. The simpler push-all-neighbors stack used in countComponents is fine for reachability but does not give correct finish times.

Time and space complexity

Edge cases

• Self-loop u→u: u is gray when it sees itself, so it is reported as a cycle, which is correct for directed graphs.
• Undirected cycle detection: every edge is seen from both ends, so ignore the edge back to the parent and only flag other visited neighbors.
• Several valid topological orders: interviewers usually accept any; do not hard-code one expected answer in your tests.
• Empty graph or isolated nodes: each isolated node is its own component and can appear anywhere in a topological order.
• Deep chains: Java's default thread stack and Python's recursion limit of about 1000 can overflow on a long path; switch to the iterative form.

Common mistakes

• Using a single boolean visited array for directed cycle detection. A black node reached through a different branch is not a cycle; only a gray node is.
• Recording the node in pre-order and reversing that for a topological sort. Only reversed post-order is guaranteed to be valid.
• Forgetting the outer loop over all nodes, which silently skips disconnected parts of the graph.
• Assuming the explicit-stack version visits nodes in the same order as recursion. Pushing neighbors reverses their order unless you push them backwards.
• Treating DFS distance as shortest distance. DFS finds a path, not the shortest one.

Variations and when to use it

Pick DFS when the question is about structure rather than distance: is everything reachable, how many groups are there, is there a cycle, which order respects these dependencies. The same skeleton powers Tarjan's bridges and articulation points (using discovery times and low-links), strongly connected components (Kosaraju runs DFS twice), and backtracking searches that enumerate every path. If you prefer a queue-based topological sort that also detects cycles by counting processed nodes, compare it with Kahn's algorithm. When the graph is a 2D grid rather than an adjacency list, see DFS on a grid.

Related LeetCode problems

• #547 Number of Provinces — count how many times the outer loop starts a fresh DFS.
• #841 Keys and Rooms — DFS from room 0 and check that every room was visited.
• #1466 Reorder Routes to Make All Paths Lead to the City Zero — DFS from city 0 over undirected edges, counting the ones that point away.
• #207 Course Schedule — three-colour cycle detection on the prerequisite graph.
• #210 Course Schedule II — the same DFS, returning reversed post-order.
• #802 Find Eventual Safe States — nodes that finish black without touching a gray node are safe.
• #1192 Critical Connections in a Network — DFS with discovery times and low-links finds bridges.

FAQ