Depth-First Search (DFS)
Commit to one path until it dead-ends, then backtrack — the traversal that turns recursion itself into a graph explorer.
Hands on Interactive visualization
Implementation Code
export function dfs(
adj: Map<number, number[]>,
node: number,
target: number,
visited = new Set<number>(),
): boolean {
if (visited.has(node)) return false; // breadcrumb already here
visited.add(node); // pre-order: act before descending
if (node === target) return true;
for (const nb of adj.get(node) ?? []) {
if (dfs(adj, nb, target, visited)) return true;
}
return false; // dead end: unwind to the last junction
}
// Iterative variant for deep graphs: explicit stack, no recursion limit.
export function dfsIter(adj: Map<number, number[]>, start: number, target: number) {
const visited = new Set<number>();
const stack = [start];
while (stack.length > 0) {
const node = stack.pop()!; // LIFO makes it depth-first
if (visited.has(node)) continue;
visited.add(node);
if (node === target) return true;
stack.push(...(adj.get(node) ?? []));
}
return false;
}Big-O Complexity
Space is the visited set plus the recursion (or explicit) stack; the stack grows with path depth, which is O(V) in the worst case — a single long chain. On wide, shallow graphs DFS's stack is far smaller than BFS's frontier.
In production When to use
Build systems, package managers, and task schedulers order dependencies by DFS post-order reversed — a node is finished only after everything it depends on, so finish times ARE the topological order.
Deadlock detection, circular-import checks, and DAG validation find cycles as back edges: an edge into a node still on the current recursion stack (the gray node in white/gray/black coloring).
Flood one DFS from each unvisited node to label components — image segmentation, network partition analysis, and union-of-islands problems. Strongly connected components (Tarjan, Kosaraju) are DFS-based too.
A maze is a graph of cells; DFS walks one corridor to its end, backtracks at dead ends, and is the natural engine when any path suffices (and randomized DFS generates the maze in the first place).
N-queens, Sudoku, subset/permutation generation, and regex engines are DFS over an implicit tree of partial solutions — go deep, fail, unwind one choice, try the next branch.
Directory tree traversal, JSON/AST visitors, and reference-following serializers are pre- or post-order DFS — the recursion mirrors the nesting of the structure itself.
Trade-offs Strengths & weaknesses
- O(V) space bounded by path depth — much lighter than BFS on wide graphs.
- The recursive form is a few lines: the call stack does the bookkeeping for free.
- Exposes deep structure BFS can't: discovery/finish times, back edges, topological order, SCCs.
- The natural engine for backtracking — state unwinds automatically as calls return.
- Can strike deep targets quickly instead of exhaustively filling every closer level first.
- Finds a path, not the shortest path — no distance guarantee whatsoever.
- Recursive form overflows the call stack on deep graphs (Python defaults to ~1000 frames).
- Can burrow far from the start before trying nearby alternatives — bad when the target is close.
- On infinite or enormous implicit graphs it can descend forever without a depth cap (IDDFS fixes this).
- Pre-order, post-order, and in-order variants answer different questions — easy to pick the wrong one.
Intuition Mental model
Maze exploration with breadcrumbs
You're in a maze with a pocket of breadcrumbs and a ball of string. Follow one corridor as far as it goes, dropping crumbs; at a dead end, rewind the string to the last junction with an untried branch. The string is the recursion stack, the crumbs are the visited set.
- Pick a corridor at each junction and keep walking = recurse into the first unvisited neighbor.
- Drop a breadcrumb in every cell you enter = mark visited, so you never re-explore.
- Dead end (or all crumbs ahead) = base case: rewind the string to the previous junction — that's the function returning.
- Back at a junction, take the next untried corridor = the loop over remaining neighbors resumes after the recursive call.
- The string's length at any moment = current recursion depth; if the maze is one giant corridor, you need a LOT of string — the stack-overflow risk.
Prep Interview questions
Detect a cycle in a directed graph. Why isn't a plain visited set enough?
Produce a topological order of a DAG using DFS.
Count islands in a binary grid.
Convert recursive DFS to iterative. What subtly changes?
When is DFS strictly the wrong choice against BFS?
Watch out Common bugs
Recursive DFS on a million-node chain blows the call stack — Python caps recursion near 1000 frames by default, and other runtimes fail at a few hundred thousand. Production code on unbounded inputs uses the iterative form with an explicit stack.
Checking visited only at the call boundary (before recursing) versus at function entry are both fine alone — mixing them, or forgetting one path (like the initial call in a components loop), yields double visits or infinite loops on cycles. Pick one convention: guard at entry is the hardest to get wrong.
Acting on a node before recursing (pre-order) versus after (post-order) changes the answer entirely: topological sort requires post-order, path-printing wants pre-order, and subtree aggregation must combine children post-order. The classic symptom is a topological sort that's simply the discovery order — wrong.
Pure reachability keeps nodes visited forever, but backtracking problems (find ALL paths, N-queens) must remove the node from the current path when the call unwinds — leaving it marked silently prunes valid solutions.
One screen Cheat sheet
Go deep first, backtrack at dead ends — a stack (usually the call stack) plus a visited set.
- Stack (LIFO) drives depth-first order — recursion is just the implicit version.
- No shortest-path guarantee: DFS finds A path, BFS finds the fewest-hops path.
- Post-order finish times reversed = topological sort; back edge to an on-stack node = cycle.
- Space tracks path DEPTH; BFS space tracks frontier WIDTH — choose by graph shape.
- Iterative form with an explicit stack avoids recursion limits on deep graphs.
- White/gray/black coloring separates 'seen' from 'still on the current path'.