Depth First Search (DFS): Dive Deep, Then Backtrack
Learn Depth First Search on a graph — the recursive dive-and-backtrack pattern, a worked walkthrough, JavaScript code, O(V+E) complexity, and common mistakes.
This article has an interactive companion
Don't just read it — step through it interactively, one state change at a time.
Depth First Search is the graph traversal you reach for when the question is "can I get there, and what's on the way?" It picks one path, commits to it all the way to a dead end, then rewinds just far enough to try the next branch. That single dive-and-backtrack rhythm is the engine under cycle detection, topological sort, connected components, flood fill, and half the "path exists" problems you'll ever see.
The whole algorithm is three lines of real logic wrapped in a recursion. Once you see how the call stack is your path, and the visited set is the only thing standing between you and an infinite loop, DFS stops being a thing you memorize and becomes a thing you derive.
The problem
You're given an undirected graph as an adjacency list: an array where index i holds the list of nodes directly connected to node i. Starting from node 0, visit every reachable node exactly once and return them in the order DFS discovers them.
Input: adjList = [[1, 2], [0, 3], [0, 3], [1, 2]]
// node 0 ↔ 1, 2 node 1 ↔ 0, 3 node 2 ↔ 0, 3 node 3 ↔ 1, 2
Output: [0, 1, 3, 2]Read the adjacency list as a map of neighbors. Node 0 connects to 1 and 2; node 3 connects to 1 and 2. It's a 4-cycle (a square). The output [0, 1, 3, 2] is DFS's pre-order discovery sequence: each node is recorded the instant it's first entered, before its neighbors are explored.
Two facts drive everything below:
- The graph can have cycles, so you must remember which nodes you've already entered — or you'll revisit forever.
- DFS goes deep before wide: it fully finishes one neighbor's entire subtree before touching the next neighbor.
The brute force baseline
The "naive" version is DFS with the safety rail removed — recurse into every neighbor, no memory of where you've been.
function dfsNoVisited(adjList, curr, result) {
result.push(curr);
for (const neighbor of adjList[curr] || []) {
dfsNoVisited(adjList, neighbor, result); // no guard!
}
return result;
}On a tree this accidentally works. On any graph with a cycle it never terminates: from 0 it enters 1, from 1 it enters 0, from 0 it enters 1… a stack overflow. Even if you cap the depth, revisiting nodes explodes the work exponentially — the same subtree gets re-explored through every path that reaches it.
The fix isn't a smarter recursion. It's one set.
The key insight: the call stack is your path, the visited set is your memory
DFS is defined by what it does when it enters a node and what "done" means:
- On entry, mark the node visited immediately and record it. Marking on entry (not on exit) is what blocks the cycle — the moment
1points back at0,0is already in the set. - Then, loop its neighbors. For each unvisited one, recurse. That recursion pushes a new frame onto the call stack, which physically represents "I'm one level deeper on this branch."
- When the loop ends, the function returns. That return is the backtrack — the stack unwinds one frame, restoring the caller as the active node so it can try its next neighbor.
You never write "backtrack" as a step. Backtracking is just a function returning. The recursion gives you a stack for free, and that stack always holds the exact path from the start node to wherever you currently are.
The optimal solution
This mirrors the algorithm the visualizer steps through: mark-on-entry, record in pre-order, recurse into unvisited neighbors, let the return unwind the stack.
function dfs(adjList, start = 0) {
const visited = new Set();
const result = [];
function explore(curr) {
visited.add(curr); // mark on entry — this is what breaks cycles
result.push(curr); // pre-order: record the node the moment we enter it
for (const neighbor of adjList[curr] || []) {
if (!visited.has(neighbor)) {
explore(neighbor); // dive deep before trying curr's next neighbor
}
// already-visited neighbors are skipped, keeping us at O(V + E)
}
// no explicit backtrack: returning here pops one call-stack frame
}
explore(start);
return result;
}Three details carry the whole thing. visited.add(curr) runs before the neighbor loop, so a cycle can never re-enter a node. result.push(curr) sits at the top of explore, making this a pre-order traversal. And the if (!visited.has(neighbor)) guard is the difference between O(V + E) and an infinite loop.
Walkthrough
Tracing adjList = [[1, 2], [0, 3], [0, 3], [1, 2]] from node 0. Watch the call stack grow as DFS dives, then shrink as it backtracks.
| Step | Action | Call stack (bottom→top) | visited | result |
|---|---|---|---|---|
| 1 | explore(0) — mark, record | [0] | {0} | [0] |
| 2 | 0's neighbor 1 unvisited → dive | [0, 1] | {0,1} | [0,1] |
| 3 | 1's neighbor 0 already visited → skip | [0, 1] | {0,1} | [0,1] |
| 4 | 1's neighbor 3 unvisited → dive | [0, 1, 3] | {0,1,3} | [0,1,3] |
| 5 | 3's neighbor 1 already visited → skip | [0, 1, 3] | {0,1,3} | [0,1,3] |
| 6 | 3's neighbor 2 unvisited → dive | [0, 1, 3, 2] | {0,1,3,2} | [0,1,3,2] |
| 7 | 2's neighbors 0, 3 both visited → skip both | [0, 1, 3, 2] | {0,1,3,2} | [0,1,3,2] |
| 8 | explore(2) returns → pop | [0, 1, 3] | {0,1,3,2} | [0,1,3,2] |
| 9 | explore(3) returns → pop | [0, 1] | {0,1,3,2} | [0,1,3,2] |
| 10 | explore(1) returns → pop | [0] | {0,1,3,2} | [0,1,3,2] |
| 11 | 0's neighbor 2 now visited → skip; return → pop | [] | {0,1,3,2} | [0,1,3,2] |
The stack peaks at depth 4 ([0, 1, 3, 2]) even though the graph is only a square — DFS chased the 0 → 1 → 3 → 2 chain to its end before unwinding at all. When it finally pops back to node 0 at step 11, node 2 is already visited, so 0's second neighbor is skipped and traversal ends. Final result: [0, 1, 3, 2].
Complexity
| Metric | Value | Why |
|---|---|---|
| Time | O(V + E) | Each of V nodes is entered once (visited guard); each edge is examined once from each endpoint |
| Space | O(V) | The visited set holds up to V nodes; the call stack reaches depth V on a linear graph |
The visited set guarantees every node's explore body runs exactly once, and inside those bodies you scan every adjacency-list entry exactly once — that's E edge inspections total (or 2E in an undirected list, still linear). Space is dominated by the recursion depth, which in the worst case (a straight chain like 0—1—2—…) equals the number of nodes.
Common mistakes
- Marking visited on exit instead of on entry. If you add to the set after the neighbor loop, a cycle re-enters the node before it's ever marked, and you loop forever. Mark the instant you enter.
- Dropping the visited guard entirely. The naive baseline above. Fine on trees, fatal on any graph with a cycle.
- Confusing pre-order and post-order.
result.push(curr)at the top gives discovery order[0, 1, 3, 2]. Move it below the loop and you get post-order — a different sequence that topological sort actually needs. Know which one your problem wants. - Forgetting disconnected components.
explore(0)only reaches nodes connected to0. If the graph has islands, wrap the call in a loop over all nodes and start a fresh DFS from any unvisited one. - Ignoring stack depth on huge graphs. Recursion depth equals path length. A 10⁵-node chain blows the native call stack — rewrite with an explicit stack array when depth can get that large.
Where this pattern shows up next
Once dive-and-backtrack clicks, these all become variations on the same recursion:
- Max Area of Island — DFS as flood fill on a grid, summing the cells each dive touches.
- Find if Path Exists in Graph — the "can I reach the target?" question, answered by whether DFS ever lands on it.
- All Paths From Source to Target — add a path list and undo-on-return, and DFS enumerates every route.
- Redundant Connection — where DFS-style traversal meets cycle detection to find the one edge that closes a loop.
You can also step through the DFS visualizer to watch the call stack tower up and collapse, the visited set fill in depth-first order, and the recursion-depth gauge track each dive in real time.
FAQ
What is the difference between DFS and BFS?
DFS goes deep before wide: it fully explores one branch to its end before backtracking to try the next, using a stack (usually the call stack via recursion). BFS goes wide before deep: it explores all neighbors at the current distance before moving further out, using a queue. DFS naturally finds a path and is ideal for cycle detection, topological sort, and connectivity. BFS finds the shortest path in an unweighted graph because it reaches nodes in order of distance from the source.
Why does DFS need a visited set?
Because graphs can contain cycles. Without tracking which nodes you've already entered, DFS follows an edge back to a node it's already inside, recurses into it again, and loops forever — a stack overflow on any cyclic graph. Marking each node visited the moment you enter it (before looping its neighbors) guarantees every node's exploration runs exactly once, which is also what keeps the total time at O(V + E) instead of exponential.
What is the time complexity of DFS?
O(V + E), where V is the number of vertices and E the number of edges. The visited set ensures each vertex's exploration body runs once, contributing the V term. Inside those bodies, every edge is examined once (twice total in an undirected adjacency list, still linear), contributing the E term. Space is O(V) for the visited set plus the recursion stack, whose depth equals the longest path — up to V nodes on a linear graph.
Should I write DFS recursively or with an explicit stack?
Recursion is cleaner and mirrors the algorithm's structure — the call stack tracks your path and returning handles backtracking automatically. But recursion depth equals the longest path, so on very large or deeply chained graphs (think 10⁵+ nodes in a line) you'll overflow the native call stack. In that case convert to an explicit stack array with push/pop, which moves the frames to the heap and removes the depth limit while traversing in the same order.
Does DFS visit every node in a disconnected graph?
Not from a single starting call. explore(0) only reaches nodes connected to node 0; any component with no path back to the start is left untouched. To cover a disconnected graph, loop over all nodes and launch a fresh DFS from each one that isn't yet visited. Each launch discovers exactly one connected component, which is precisely how you count components or label islands.
Make it stick: run this one yourself
Don't just read it — step through it interactively, one state change at a time.