CONCEPT · Specialist
Depth-first search
also recursion · backtracking search
Dive along one path with a stack or recursion. Best for connectivity, cycles, topological finishing times, and search trees — not unweighted shortest paths.
Intuition
Go as far as you can, then unwind. The call stack is the path.
When to reach for it
- Connected components
- Cycle detection
- Tree DP, backtracking (n ≤ 20)
Usual pits
- Recursion limit on deep chains
- Forgetting to unmark in backtracking (or marking when you should not)