8. BFS vs DFS
- The core difference: exploration order
- Data structures: queue vs stack (or recursion)
- What each traversal produces (trees + metadata)
- When BFS is the right tool
- When DFS is the right tool
- Complexity comparison
- Common pitfalls & engineering guidelines
BFS and DFS are the two fundamental graph traversals. They look similar in code, but their structural behavior is different: BFS expands by layers; DFS dives deep along a path.
This part gives you a practical mental model: how to choose the right one quickly.
8.1 Core Difference: Exploration Order
The order is not cosmetic: it changes what you can guarantee. BFS guarantees shortest paths in unweighted graphs; DFS does not.
8.2 Queue vs Stack
The data structure dictates the traversal:
- BFS uses a queue (FIFO) → preserves layers.
- DFS uses a stack (LIFO) (explicit) or recursion (implicit call stack).
8.3 Side-by-Side Comparison
| Aspect | BFS | DFS |
|---|---|---|
| Exploration | Layer by layer | Deep then backtrack |
| Data structure | Queue (FIFO) | Stack (LIFO) / recursion |
| Shortest paths (unweighted) | Yes | No |
| Typical outputs | Distances + predecessor tree | Discovery/finish times, DFS tree/forest |
| Best for | Minimum hops, layers, nearest target | Structure, cycles, topological order, SCC |
| Complexity | O(|V|+|E|) | O(|V|+|E|) |
8.4 What BFS Produces
BFS produces two “usable” artifacts:
d[v]— shortest distance from s to v (in edges)π[v]— predecessor pointers, forming a BFS tree
8.5 What DFS Produces
DFS is best seen as a “structure extractor”. Common DFS metadata:
- discovery time (tin[v]) and finish time (tout[v])
- DFS tree / forest
- edge classification (tree, back, forward, cross) — in directed graphs
8.6 When to Choose BFS
Choose BFS when edges represent unit transitions and you care about:
- minimum number of steps (shortest path in hops)
- nearest target (early exit when you first reach it)
- layers / wavefront (broadcast, diffusion, degrees of separation)
- grid shortest moves (maze, robotics on 2D maps)
8.7 When to Choose DFS
Choose DFS when you need deep structure or global graph properties:
- topological sorting (DAG scheduling)
- cycle detection (especially in directed graphs)
- connected components (also possible with BFS, but DFS is common)
- strongly connected components (Kosaraju, Tarjan)
- backtracking / state-space search (when you must explore choices)
8.8 Complexity
With adjacency lists, both traversals run in:
Differences are usually in memory profile:
- BFS may store an entire frontier (worst-case: large queue).
- DFS stores a path plus recursion/stack (depth-dependent).
8.9 Common Pitfalls & Guidelines
- Mixing goals: using DFS when you need shortest paths (wrong tool).
- Late marking: in BFS, mark visited when enqueuing, not when dequeuing (avoids duplicates).
- Disconnected graphs: to traverse everything, run BFS/DFS from each unvisited vertex.
- Weighted edges: BFS is not for weighted shortest paths → use Dijkstra / 0-1 BFS.
Series Complete
You now have the full BFS toolkit: intuition (layers), formal algorithm, correctness proof, complexity analysis, tree/path reconstruction, applications — and how BFS compares to DFS.
- Revisit the BFS Series Overview
- Practice on grids and shortest-hop problems (BFS + path reconstruction)
- Move on to DFS fundamentals and topological sorting