8. DFS vs BFS
- The core contrast between DFS and BFS
- Stack vs queue
- What BFS naturally computes
- What DFS naturally computes
- A side-by-side comparison
- When DFS is the right tool
- When BFS is the right tool
- Complexity comparison
- Common misconceptions
- Series summary and closing
DFS and BFS are the two fundamental graph traversal strategies. They both explore graphs in linear time, but they reveal different kinds of structure.
BFS is distance-oriented. DFS is structure-oriented.
8.1 The Core Difference
The fundamental contrast is:
- BFS explores the graph layer by layer.
- DFS explores one path deeply before backtracking.
This difference changes not only the traversal order, but also the kind of information each algorithm naturally exposes.
8.2 Queue vs Stack
The data structure behind each traversal explains its behavior:
- BFS uses a queue (FIFO).
- DFS uses a stack (explicit or implicit via recursion).
8.3 What BFS Naturally Computes
BFS is the natural tool when we care about distance from a source.
- shortest paths in unweighted graphs
- layer structure
- minimum number of moves
- reachability by hop count
This is why BFS is the standard algorithm for shortest paths in unweighted graphs.
8.4 What DFS Naturally Computes
DFS is the natural tool when we care about graph structure.
- discovery and finish times
- ancestry relations
- edge classification
- cycle detection
- topological sorting
- strongly connected components
DFS turns traversal into a structural decomposition method.
8.5 Side-by-Side Comparison
| Aspect | BFS | DFS |
|---|---|---|
| Main strategy | Explore by layers | Explore deeply, then backtrack |
| Primary data structure | Queue | Stack / recursion |
| Best for | Distance and shortest paths | Structure and decomposition |
| Shortest path in unweighted graphs | Yes | No |
| Cycle detection | Possible, but not natural | Natural and elegant |
| Topological sorting | No | Yes |
| Strongly connected components | No | Yes |
| Time complexity | O(|V|+|E|) | O(|V|+|E|) |
8.6 When to Prefer DFS
Choose DFS when the problem asks for structural information such as:
- Does the graph contain a cycle?
- Can the graph be topologically sorted?
- What are its strongly connected components?
- Which vertices are ancestors/descendants in the exploration tree?
8.7 When to Prefer BFS
Choose BFS when the problem asks for distance-like information such as:
- What is the shortest path in an unweighted graph?
- What is the minimum number of steps?
- Which vertices lie in layer 1, 2, 3, ... from a source?
8.8 Complexity
With adjacency lists, both traversals run in:
So the main difference is not asymptotic complexity, but the kind of information each traversal exposes.
8.9 Common Misconceptions
- “DFS can also find shortest paths.” Not in general.
- “BFS and DFS are interchangeable.” They are not; they solve different structural goals.
- “DFS is only recursion.” DFS is a traversal principle; recursion is just one implementation style.
8.10 Series Summary
Across this DFS series, we studied:
- the graph model and exploration problem
- deep exploration and backtracking
- the formal DFS algorithm
- discovery and finish times
- edge classification
- cycle detection and topological sorting
- strongly connected components
Series Complete
This closes the Depth-First Search series. You now have both the formal algorithmic view and the structural perspective needed to apply DFS in theoretical and engineering contexts.