Why This Matters
BFS and DFS visit the same reachable component in many graphs, but they answer different questions. BFS is about levels and unweighted shortest paths. DFS is about depth, structure, and exhaustive exploration.
Decision Rule
Use BFS when the problem asks for minimum moves, fewest edges, nearest target, or level order. Use DFS when the problem asks for reachability, connected components, cycle structure, topological reasoning, backtracking, or exploring all possibilities.
Comparison Table
| Feature | BFS | DFS |
|---|---|---|
| Data structure | queue | stack or recursion |
| Traversal shape | wavefront by distance | dive and backtrack |
| Unweighted shortest path | yes | no guarantee |
| Space risk | wide frontiers | deep recursion |
| Common patterns | grid shortest path, multi-source spread | components, cycle detection, backtracking |
| Python warning | use deque | recursion depth can fail |
Worked Example
In a maze where every move costs one step, BFS from the start finds the exit with the fewest moves because it explores all cells at distance k before distance k + 1.
DFS may find an exit quickly, but it can take a long detour first. It proves reachability, not minimum distance.
Common Mistakes
| Mistake | Correction |
|---|---|
| Using DFS for "minimum number of moves." | Use BFS for unweighted shortest path. |
| Assuming BFS is always better. | DFS is simpler for components, recursive structure, and backtracking. |
| Forgetting visited state. | Both can loop forever on cyclic graphs without a visited set. |
Diagnostic Questions
| Question | Answer signal |
|---|---|
| Which traversal finds shortest unweighted paths? | BFS. |
| Which traversal naturally matches recursion? | DFS. |
| Can DFS solve connected components? | Yes, as can BFS. |
| Why can BFS use more memory? | It may store an entire frontier level. |
Exercises
- Beginner: Run BFS and DFS by hand on the same small graph.
- Beginner: Choose BFS or DFS for a tree level-order traversal.
- Beginner: Choose BFS or DFS for counting islands in a grid.
- Intermediate: Implement both traversals with a shared adjacency list.
- Intermediate: Explain why multi-source BFS solves nearest-source problems.
- Challenge: Convert recursive DFS cycle detection into iterative DFS with explicit stack states.
References
- MIT OpenCourseWare. 6.006 Introduction to Algorithms, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/
- MIT OpenCourseWare. 6.006 Graph search materials, Spring 2020: https://ocw.mit.edu/courses/6-006-introduction-to-algorithms-spring-2020/