Why This Matters
BFS is the shortest-path algorithm for unweighted graphs. It also appears in crawlers, dependency expansion, social-distance queries, puzzle search, and level-order tree traversal.
Core Idea
BFS uses a queue. Start with one vertex, mark it visited, then repeatedly remove the front vertex and enqueue its unvisited neighbors.
Worked example: if vertex S connects to A and B, and A connects to C, BFS visits S, then A and B, then C. The first time C is discovered gives its shortest unweighted distance from S.
Common Mistakes
- Marking visited too late. Mark when enqueuing to avoid duplicate queue entries.
- Using BFS for weighted shortest paths. Edge weights require Dijkstra or another weighted algorithm.
- Forgetting disconnected components. One BFS from one start may not visit the whole graph.
Exercises
- Run BFS by hand on a four-node graph.
- Explain why FIFO order gives increasing distance.
- Modify BFS to store parent pointers for path reconstruction.
Next Topics
References
- Cormen, Leiserson, Rivest, Stein. Introduction to Algorithms (4th ed., 2022). Ch. 20.
- Skiena. The Algorithm Design Manual (3rd ed., 2020). Ch. 7.