CONCEPT · Specialist
Breadth-first search
also level order · unweighted shortest path
Explore layer by layer with a queue. First hit on an unweighted graph is a shortest path. Also the engine of flood fill when you want a wavefront.
Intuition
The queue is the current frontier. Distances on that frontier are equal, and they only increase.
When to reach for it
- Shortest path with equal edge weights
- Minimum moves in a grid
- Bipartite check, 0-1 layers
Usual pits
- Marking visited too late (duplicate queue entries)
- Using shift() in JS
- Using DFS and claiming the path is shortest