Overview
Depth-First Search explores as far as possible along each branch before backtracking.
Analogy
Walking a maze: follow one corridor to the end, backtrack, try the next.
Step-by-step
- Start at node; mark visited.
- For each neighbor:
- If unvisited, DFS(neighbor).
- Backtrack when no unvisited neighbors remain.
- Record order if needed (pre/post).
Visual
Recursive call stack forms a path; unwinds on backtrack.
Common mistakes
- Marking visited after the recursive call (creates cycles).
- Deep recursion on huge graphs without iterative fallback.
- Confusing pre-order vs post-order uses.
Practice questions
- List discovery/finish times on a small directed graph.
- Detect a cycle in a directed graph with colors (white/gray/black).
- Topologically sort using DFS post-order.
Space
O(V) recursion/stack
AI Wisdom