Algorithms · intermediate
Depth-first search
Depth-first search explores one graph path as far as possible before backtracking, using recursion or an explicit LIFO stack to retain unfinished alternatives.
Why it matters
DFS reveals structural properties such as reachability, cycles, components, and traversal order while using memory proportional to the active depth plus visited state.
Mental model
How to reason about depth-first search
Enter a vertex, suspend its remaining neighbors, and continue into one unvisited neighbor. When no continuation remains, resume the newest suspended vertex.
Analogy
Exploring a maze by taking one corridor until it ends, then returning to the most recent junction with an unexplored branch.
Examples
See the boundary, not just the happy path
Worked example · Detect a directed cycle
visited plus an active-recursion-stack markerAn edge to an active ancestor is a back edge and proves a directed cycle; a globally visited marker alone cannot distinguish it.
Worked example · Iterative traversal
stack.push(start); node = stack.pop()An explicit stack reproduces the unfinished-work role of recursive call frames and avoids language recursion limits.
Useful contrast · Shortest paths
DFS reaches a destination through a long branch before a short oneFirst discovery by DFS does not guarantee a minimum-edge path; traversal depth is chosen before distance.
Common mistakes
Misconceptions to remove early
Omitting visited state on a cyclic graph
The traversal can revisit the same cycle indefinitely. Mark vertices according to the algorithm's discovery invariant.
Assuming recursive DFS is memory-free
Each active call consumes a stack frame. A path of extreme depth can overflow the call stack even though total work is linear.
Quick check
Can you predict the result?
1. Which structure determines the next unfinished branch in DFS?
- • A LIFO stack, explicit or represented by recursive calls
- • A FIFO queue
- • An adjacency matrix alone
2. Why does a simple visited set not by itself detect directed cycles?
Keep building