BFS visits all vertices at distance from the start before any at distance . Implementation: a queue plus a "visited" set. Enqueue the start; loop: dequeue, mark visited, enqueue each unvisited neighbor.
Why level-order
Because the queue is FIFO, the first time you dequeue a vertex it's via the shortest unweighted path from the start. This gives BFS its signature use: shortest path in unweighted graphs. You can also reconstruct the path by storing each vertex's parent at dequeue time.
Complexity
— every vertex is enqueued/dequeued once, every edge is examined twice (once from each endpoint, in an undirected graph). Space is for the queue and visited set.
Multi-source BFS
Start BFS from multiple sources at once by enqueueing all of them initially. The result is the distance from each vertex to the nearest source. Useful for problems like "fill empty rooms with their distance to the nearest gate" or "rotten oranges spreading through a grid."
0-1 BFS
When edges have weights of only 0 or 1, BFS with a deque solves shortest paths in instead of needing Dijkstra. Push 0-weight edges to the front, 1-weight to the back. Useful in puzzle/grid problems where some moves are "free."
Patterns to recognize
- Shortest path on grid / unweighted graph
- "Minimum number of moves" / "fewest transformations" problems (word ladder, knight on chessboard)
- Level-order tree traversal (a tree is just a special graph)
- Connected components — repeated BFS from each unvisited vertex
Common bug
Marking a vertex visited only when you *dequeue* it instead of when you *enqueue* it. The second variant lets the same vertex enter the queue many times before it's first visited — correct but wasteful. Mark on enqueue.