Depth-First Search
Plunge as deep as possible along each branch, then backtrack — the traversal behind spanning trees, cycle detection, and topological order.
Depth-First Search
Depth-first search (DFS) explores a Graph like someone wandering a maze with one hand on the wall: follow a corridor as far as it goes, and only when you hit a dead end do you backtrack to the last junction with an unexplored passage. Where Breadth-First Search fans out cautiously in layers, DFS commits — it races down a single branch to its end before considering any alternative.
This deep-first, backtrack-when-stuck discipline is captured by a stack (last-in, first-out), or equivalently by recursion, which uses the call stack for you.
The algorithm
To run DFS from a node u: mark it visited, then recurse into each unvisited neighbor in turn. When a node has no unvisited neighbors left, the recursion unwinds — that unwinding is the backtracking. Like BFS, every vertex and edge is examined once, so DFS runs in O(V + E).
What depth buys you
Diving deep is the wrong tool for shortest paths — the first time DFS reaches a node it may have taken a wildly roundabout route. But the structure DFS leaves behind is exactly what several classic problems need:
- Spanning trees. The edges DFS actually follows form a DFS tree — a connected, loop-free subgraph touching every reachable node. (BFS produces its own spanning tree, shallower and bushier.)
- Cycle detection. If DFS ever encounters an edge leading back to a node still on the current stack — a back edge — the graph contains a cycle. This is how you check whether a dependency graph is acyclic.
- Ordering. Recording nodes as their recursion finishes yields a topological order of a directed acyclic graph: build steps, course prerequisites, spreadsheet recalculation.
A maze is a depth-first tree
Maze generation makes DFS tangible. Carve a grid by walking depth-first from a starting cell, knocking down a wall whenever you step to an unvisited neighbor; when you get stuck, backtrack. The single winding corridor with no loops that results is precisely a DFS spanning tree — every cell reachable, exactly one path between any two.