Breadth-First Search
Explore a graph level by level with a queue. On unweighted graphs this gives you shortest paths almost for free.
Key ideas
- —A FIFO queue processes nodes in order of increasing distance from the source.
- —On unweighted graphs, the first time you reach a node is via a shortest path.
- —Mark nodes visited when you enqueue them, not when you dequeue, to avoid duplicates.
Why a queue gives shortest paths
BFS dequeues every node at distance d before any node at distance d+1, because neighbors are enqueued in layers. That ordering means the first time a node is reached, it is reached by a minimum number of edges. This is the engine behind grid shortest-path problems and word-ladder transformations.
Multi-source and layer counting
Seed the queue with several starting nodes at once to compute distances from the nearest source — exactly what you want for problems like rotting oranges spreading to neighbors. Track the queue size at the start of each round when you need to count discrete levels, such as the minutes elapsed or the depth of a tree.
Practice this
Sources
- Breadth-first searchWikipedia
- Breadth-First SearchCP-Algorithms