What is depth-first search?
Depth-first search explores as far as possible down one path before backtracking. From the current node it
steps into the first unvisited neighbor, then that neighbor's first unvisited neighbor, and so on — only
backing up once it hits a dead end. A stack remembers where to back up to, whether that stack is
explicit or it's simply the call stack running your recursion.
- Stack
- Remembers where to backtrack to — either the call stack or an array you manage yourself
- Visited
- A marker set so you never re-enter a node you've already explored
- Backtrack
- Stepping back to the last unexplored branch once the current path hits a dead end
Why depth-first search at all?
Picture exploring a maze with one rule: always take the first unexplored turn and keep going until you either reach the exit or run out of turns. Only then do you back up to the last junction that still had an unexplored option, and try that instead.
That's depth-first search — commit to a path, go all the way down it, and only retreat when it's a provable dead end. (Checking every nearby room before going further is a different strategy — breadth-first search — worth knowing exists, though it's a story for another page.)
One branch runs into a wall on every side — back up and try the one still open.
What kinds of problems does it solve?
Three common shapes. The traversal rule never changes — you only change what you do at each node and when you decide to stop.
Does a path exist?
Start at the source and walk down neighbors, marking each one visited. The moment you land on
the target, you're done — you don't need the shortest way there, just a way there.
Stop the instant the target lights up. No need to keep exploring after that.
Find all paths
Instead of stopping at the first match, keep going: whenever you reach the target, record the current path, then backtrack and try the next branch anyway.
Reaching the target doesn't stop the search — it just records one answer.
Detect a cycle
Track which nodes are on the current path, not just visited overall. If a neighbor points back
to a node that's still on that path, you've found a cycle.
C's only unvisited-looking neighbor is A — but A never left the stack.
Two types
Same traversal order either way — the only difference is who keeps track of where to backtrack to: the language's call stack, or an array you push and pop yourself.
Recursive
Each call to dfs(node) goes one level deeper by calling itself on a neighbor. When a call
returns, you're automatically back where you left off — the call stack did the bookkeeping for free.
Simplest to write, but it can overflow on a graph that's deep enough.
Every return pops a frame — you never touch the stack directly.
function dfs(node: Node, visited: Set = new Set()): void {
if (visited.has(node)) return; // already explored, nothing to do
visited.add(node);
for (const neighbor of node.neighbors) {
dfs(neighbor, visited); // go all the way down before trying the next neighbor
}
// implicit return here backtracks to the caller automatically
}
Iterative
Push the starting node onto an explicit stack array. Pop a node, and if it's unvisited, mark
it and push its neighbors. Same last-in-first-out order as recursion produces — but now you own the
stack, so depth is limited by memory, not by call frames.
Nothing here is automatic — every push and pop is a line you wrote.
function dfsIterative(start: Node): void {
const stack: Node[] = [start];
const visited = new Set();
while (stack.length > 0) {
const node = stack.pop()!; // LIFO — most recently pushed goes first
if (visited.has(node)) continue;
visited.add(node);
for (const neighbor of node.neighbors) {
stack.push(neighbor); // queued for later, deepest-pushed explored first
}
}
}
Where it works — and where it breaks
Depth-first search guarantees it will find a path if one exists. It does not guarantee that path is the shortest one — it just happens to be whichever path it committed to first.
Works for "does a path exist"
Reachability doesn't care how you got there. Depth-first search will eventually visit every node connected to the start, so if the target is reachable, it will be found.
Breaks for "find the shortest path"
Depth-first search has no notion of distance — it just commits to the first neighbor it sees. In an
unweighted graph, that's breadth-first search's job: it explores level by level, so the first
time it reaches a node is guaranteed to be by the shortest route.