ƒ(x) GraphIntermediate interactive
Depth-First Search
Plunge down one path before backtracking.
graph_dfs
step 1 / 14
Start DFS at A.
frontiercurrentvisited
speed1×
How it works
DFS dives as deep as possible along each branch before backtracking, using a stack (or recursion). It's the workhorse for cycle detection, topological sort, connected components, and maze solving.
Mental models
- Recursion uses the call stack; iterative DFS uses an explicit one.
- Pre/post-order around the recursive call power many graph algorithms.
Complexity
- Time
- O(V + E)
- Space
- O(V)recursion / stack
Reach for it when
- Cycle detection
- Topological sort
- Connected components