Depth-first search

The problem it solves

Some questions about a graph are about reaching: is there any path from here to there? Which nodes form connected clumps? Does this dependency graph contain a cycle? Can this maze be escaped at all? None of these care about shortest — they care about exhaustively exploring everything reachable, cheaply, with minimal ceremony. Depth-first search is the exhaustive explorer: it commits to one path, follows it to the bitter end, backs up the minimum necessary, and tries the next branch, until nothing reachable remains unvisited.

Its second life is bigger than graphs: DFS is recursion’s traversal order. Every backtracking search (N-Queens, sudoku, permutations), every tree walk, every “explore all configurations” problem is DFS over an implicit graph whose nodes are states. Learn its mechanics once and you’ve learned the skeleton of a third of the interview canon.

The intuition — and where it breaks down

Exploring a cave system with a ball of string. At every junction, pick an unexplored tunnel and go. Dead end? Follow the string back to the last junction with an untried tunnel and take it. The string is the whole trick: it records the path you came by, and backtracking means rewinding it — never teleporting, never re-planning, just unwinding to the most recent choice point.

In code, the string is the call stack. Each recursive visit(node) call is a knot; returning from the call is rewinding to the previous knot. This is why the visualization draws the call-frame panel next to the graph: the stack at any pause is the current path from the start to the active node, knot for knot — watch it grow down a branch and unwind at a dead end, and recursion stops being magic.

Where the analogy breaks, instructively: a caver at a junction sees which tunnels look promising; DFS takes them in arbitrary (here: alphabetical) order with zero judgment. And a caver notices they’ve looped back to a familiar junction by recognizing it — DFS must carry an explicit visited set, because without one it will happily walk A → B → A → B forever. The string prevents getting lost; only the visited set prevents going in circles. They are different jobs, and conflating them is a real bug source.

Loading…

A walkthrough you can check

Graph: A—B, A—C, B—D, C—D. Start at A, neighbours in alphabetical order.

1. Visit A (stack: A). First unvisited neighbour: B.
2. Visit B (stack: A,B). Its neighbours: A — visited, rejected; D — new.
3. Visit D (stack: A,B,D). Neighbours B (visited), C — new.
4. Visit C (stack: A,B,D,C). Neighbours A (visited!), D (visited). Dead end — backtrack: C’s frame pops.
5. Back at D: no more neighbours. Pop. Back at B: none. Pop. Back at A: next neighbour C — already visited via the deep path. Rejected. Pop. Done.

Preorder: A, B, D, C. The moment worth staring at is step 4–5: C was reached the long way round (A→B→D→C, three edges) even though A—C is one edge. BFS would have found C at distance 1. Nothing went wrong — DFS answers “reachable?”, and C is reachable — but any instinct that DFS paths are short must die here, preferably before an interviewer kills it for you.

The invariant

The call stack is exactly the path from the start to the node currently being explored — every node on it is an ancestor of the active node. From this, the cycle-detection machinery falls out. In a directed graph, meeting a node that is on the stack (grey, in white–grey–black colouring) means you’ve found a path back to your own ancestor: a cycle, guaranteed. Meeting a node that’s merely visited-and-finished (black) proves nothing about cycles. In an undirected graph, any visited neighbour other than your immediate parent closes a cycle. Interviewers ask cycle detection constantly, and both correct answers are one sentence each given the invariant — which is why the invariant is the thing to actually know.

Post-order (when a node’s frame pops) carries its own gold: a node finishes only after everything reachable from it has finished. Reverse the finish order of a DAG and you have a topological sort; run DFS on the reversed graph in finish order and you have Kosaraju’s strongly-connected components. Half of graph theory’s classic algorithms are “DFS, but pay attention to when frames pop”.

Complexity, derived

Each node is visited once (the set guarantees it): O(V) frames pushed and popped. From each node, every incident edge is inspected exactly once — over the run, each edge is considered from at most both ends: O(E). O(V + E) total, and the trace’s counters (nodes visited, edges inspected, calls) let you check the count instead of trusting it.

Space is the sneaky one: O(V) for the visited set, but also O(V) worst-case for the stack — a path-shaped graph drives recursion n deep. In most language runtimes that’s a stack overflow around depth 10⁴–10⁵, which means recursive DFS on a large real dataset is a latent crash. The iterative rewrite (explicit stack of nodes) trades elegance for safety, with one subtlety: pushing neighbours onto a LIFO stack visits them in reverse order relative to the recursive version — same coverage, different preorder, and tests comparing traversal sequences will notice.

What people get wrong

“DFS finds the shortest path.” The walkthrough above is the counterexample; keep it loaded. DFS finds a path, with no length guarantee whatsoever.

Cycle detection with the wrong colour test. Directed graphs need the on-stack (grey) check; testing merely-visited yields false positives on shared substructure (two paths converging on a node is not a cycle). Undirected graphs need the parent exemption, or every single edge “detects” the two-node cycle A–B–A.

Global visited versus per-path state. Graph traversal wants one global visited set — a node explored once is done. Backtracking wants path-local state that’s undone on return (a queen removed, a choice unmade). DFS-the-traversal and DFS-the-backtracking-skeleton share code shape but differ exactly here, and importing the wrong convention produces either exponential blowup or missed solutions.

Forgetting the disconnected case. visit(start) explores one component. “Count the islands”-type problems need the outer loop: for every node, if unvisited, launch a fresh DFS and increment the count.

Implementation notes across languages

Python: the default recursion limit (~1000) makes recursive DFS on any serious input a RecursionError; sys.setrecursionlimit is a band-aid with segfault risk — write it iteratively for real data. Java/C++: thread stacks give you more depth but the cliff still exists; competitive programmers routinely convert to iterative for n ≥ 10⁵. JavaScript: no tail-call optimization in practice, same cliff. In all languages the iterative version’s stack should hold nodes (or node+neighbour-index pairs for exact preorder parity), and the visited check belongs at push time or at pop time — pick one and be consistent, because mixing them re-pushes shared nodes and quietly inflates the stack.