DFS is the explorer who walks a corridor to its dead-end, backs up to the last fork, and tries the next corridor — never leaving a path half-explored.
Instead of a queue, it uses a stack (or recursion), diving as deep as possible along one branch before backtracking. The trade-off vs BFS: DFS needs far less memory on deep graphs, but it does not find shortest paths.
How It Works
- Initialize: push the starting node onto the stack.
- Process: pop the top node; if unvisited, mark it visited.
- Explore: push all unvisited neighbors onto the stack.
- Repeat: continue until the stack is empty. The pop order defines the DFS traversal.
The recursive form is even simpler: visit(u) { mark u; for each neighbor v: if !visited[v]: visit(v) }.
Key Insight
The stack’s LIFO discipline means the most recently discovered node is always explored first — that produces “depth” instead of “breadth.”
The real power is in when a node is marked:
- Preorder (when first encountered) gives traversal order.
- Postorder (after all descendants finish) makes DFS the right tool for topological sorting and strongly connected components, because it records “a node before everything reachable from it.”
Worked Example
Run DFS on the visualizer’s default undirected graph (start A), visiting neighbors in order:
- Visit A → push B, C → stack
[B, C]→ pop C. - Visit C → push E, F → stack
[B, E, F]→ pop F. - Visit F → neighbors C, E already visited → nothing → pop E.
- Visit E → push D → stack
[B, D]→ pop D. - Visit D → neighbors B, E visited → pop B → visit B → done.
DFS order: A, C, F, E, D, B. Contrast this with BFS’s A, B, C, D, E, F — DFS chases one branch deep before ever touching the other side of the graph.
Edge Cases & Pitfalls
- Disconnected graphs — DFS from one start only covers its component: restart from unvisited nodes to cover everything.
- Cycles — the visited set is essential; without it, DFS loops forever.
- Recursive stack overflow — on very deep graphs (e.g., a 10⁶-node chain), the call stack overflows. Use an explicit stack or increase the limit.
- Memory on wide graphs — DFS stores only the current path: much leaner than BFS on wide graphs.
Comparison: DFS vs BFS
| Aspect | DFS | BFS |
|---|---|---|
| Data structure | LIFO stack / recursion | FIFO queue |
| Shortest path (unweighted) | No | Yes |
| Memory on wide graphs | Low (path only) | High (queue) |
| Applications | Topo sort, cycles, SCCs | Shortest paths, levels |
Applications
- Topological sorting — postorder DFS on a DAG
- Cycle detection — a back edge to an in-progress ancestor reveals a cycle
- Strongly connected components — Kosaraju/Tarjan both start with DFS
- Maze / puzzle solving — finds some path (not necessarily shortest)
- Connected components — flood-fill style labeling
Practice Trajectory
- Hand-trace DFS on the visualizer graph starting at D, writing the stack after each pop.
- Distinguish preorder from postorder and state which one topological sort uses.
- Explain how a “back edge” (edge to a currently in-progress node) detects a cycle.
- Contrast the memory profiles of BFS and DFS on a wide graph.
- Implement DFS iteratively with an explicit stack, then recursively, and compare the visit orders.