Exploring in rings
Breadth first search, or BFS, fans out from a starting vertex one ring at a time. It visits every vertex at distance one, then every vertex at distance two, and so on. A queue holds the frontier so vertices are processed in the exact order they were discovered.
Why the order matters
Because BFS reaches nearer vertices before farther ones, the first time it touches a vertex is along a shortest path measured in number of edges. This makes BFS the natural tool for unweighted shortest paths.
Common applications
- Shortest path in unweighted graphs: record each vertex's discovery distance and predecessor.
- Reachability: any vertex BFS marks is reachable from the start.
- Connected component sizes: count what one BFS sweep visits.
- Level grouping: things like social network degrees of separation fall out directly.
To avoid revisiting work, mark each vertex as seen the moment it enters the queue, not when it leaves. That prevents the same vertex from being enqueued many times.
Key idea
BFS explores level by level using a queue, so the first time it reaches a vertex it has found a shortest path by edge count in an unweighted graph.