Graph Traversal - Depth First Search(DFS)

Depth-First Search dives down one path as far as edges allow, using a stack (explicit or the call stack) to remember where to backtrack to, so it commits to a branch before ever looking sideways — that single choice is what separates it from BFS.

Recognize the pattern

• Problem talks about paths, connectivity, cycles, topological order, or exhaustively exploring configurations (backtracking, maze/flood-fill).
• You need to go 'as deep as possible first' — e.g. detect a cycle, find connected components, compute finish times for topological sort.
• Memory matters relative to graph width: DFS's stack holds one root-to-leaf path, not a whole frontier like BFS.
• You do not need shortest path in an unweighted graph — that tell points to BFS instead.

Brute force → optimal

Brute force: no adjacency list — rescan the full edge list to find each node's neighbors. That's O(V) per lookup, O(V·(V+E)) overall, and without a visited set it loops forever on any cycle.

Optimal: adjacency list (O(1)-amortized neighbor iteration) plus a visited array so every vertex is entered once and every edge is scanned once. That's the version below.

Complexity, derived from first principles

Time. Each vertex is pushed/recursed into and marked visited exactly once → V unit operations. Each vertex's adjacency list is scanned exactly once when that vertex is processed; summed across all vertices this totals the sum of adjacency-list lengths — 2E for an undirected graph (each edge sits in two lists) or E for a directed graph. Total work = O(V) + O(E) = O(V + E).

Space. visited[]: O(V). Call stack (or explicit stack): worst case equals the longest simple path from the start, up to O(V) for a skewed/path-shaped graph. Adjacency list itself: O(V + E). Overall auxiliary space beyond the input graph: O(V).

Traced worked example

Graph (undirected), adjacency lists: A:[B,C], B:[A,D], C:[A,D], D:[B,C,E], E:[D]. Start at A, recursive DFS, neighbors visited in list order. Only 4 of the 5 edges are ever followed (become tree edges); edge A-C is checked but never followed because C is already visited by the time A looks at it.

Visit order: A, B, D, C, E. Every one of the 5 edges was inspected exactly twice (10 = 2E checks), but only 4 edges (A-B, B-D, D-C, D-E) were ever followed — the 5th inspection, A-C, is a back-edge to an already-visited node and contributes to the O(V+E) check count without adding a tree edge. Every vertex entered once — matches O(V+E).

Step through it yourself

The debugger below runs DFS on a small undirected graph with cycles. Watch the call stack grow as it dives deep, nodes turn green as they're visited, and — the crux — at every edge you predict whether the neighbour is already visited (skip) or new (recurse). The skips are exactly the cycle edges the visited set saves you from.

Code — recursive and iterative

import java.util.*;

public class DFS {
    // Recursive DFS
    static void dfs(int node, List> adj, boolean[] visited, List order) {
        visited[node] = true;
        order.add(node);
        for (int next : adj.get(node)) {
            if (!visited[next]) dfs(next, adj, visited, order);
        }
    }

    // Iterative DFS with an explicit stack
    static List dfsIterative(int start, List> adj, int n) {
        boolean[] visited = new boolean[n];
        List order = new ArrayList<>();
        Deque stack = new ArrayDeque<>();
        stack.push(start);
        while (!stack.isEmpty()) {
            int node = stack.pop();
            if (visited[node]) continue; // may be pushed multiple times
            visited[node] = true;
            order.add(node);
            List neighbors = adj.get(node);
            for (int i = neighbors.size() - 1; i >= 0; i--) {
                int next = neighbors.get(i);
                if (!visited[next]) stack.push(next);
            }
        }
        return order;
    }
}

Note the iterative version checks visited on pop, not on push, because a node can be pushed by more than one neighbor before it is ever processed — skipping that check double-processes nodes and breaks the O(V+E) bound.

Pitfalls

• Forgetting visited entirely, or marking it on pop instead of push in recursion — causes infinite recursion / stack overflow on cyclic graphs.
• In the iterative version, marking visited on push instead of pop silently changes which node 'wins' when two branches reach the same neighbor, and can revisit nodes if not guarded on pop.
• Deep recursion on a large, sparse, chain-like graph (e.g. a linked-list-shaped graph of 100k nodes) blows the JVM call stack — convert to the iterative form when depth is unbounded.
• Disconnected graphs: a single dfs(start) call only reaches one component — loop over all vertices and call dfs on every unvisited one to cover the whole graph.
• Conflating 'edge inspected' with 'edge followed': every edge is checked twice (undirected) even though only V−1 of those checks become tree edges — the rest are back-edges to already-visited nodes, which is exactly what cycle detection relies on.

When to use / when not — vs BFS

Use DFS for: cycle detection, topological sort, connected components, exhaustive/backtracking search (permutations, maze solving), computing tree properties (heights, articulation points) — anywhere the recursive 'go deep, then back out' structure matches the problem, and where its O(V) space (vs frontier width) is the smaller footprint.

Use BFS instead when you need the shortest path / minimum number of edges in an unweighted graph, or level-order processing — DFS can find a path but gives no shortest-path guarantee, and it may explore a much longer path first, wasting time on problems where proximity matters.

Trade-off summary: DFS space is bounded by the longest path (good for deep, narrow graphs); BFS space is bounded by the widest frontier (good for shortest-path guarantees but can blow up on wide graphs).

Takeaways

• DFS = commit-then-backtrack; correctness and O(V+E) both come from marking visited exactly once per vertex.
• Recursive DFS uses the call stack implicitly; iterative DFS needs an explicit stack and must check visited on pop, not push.
• Tree edges (followed) and back-edges (checked, already visited) are different things — the visit order only reflects tree edges; every non-tree edge is a skipped check, not a step.
• Reach for DFS when the question is about structure/reachability/exhaustive search; reach for BFS when it's about shortest paths or levels.

Recall: Why must the iterative stack-based DFS re-check visited after popping a node, even though it also checked before pushing?

Derived from graph theory fundamentals (Cormen et al., Introduction to Algorithms) and standard DFS traversal treatments.