Breadth-first search

Summary

Breadth-first search (BFS) explores a graph from a source vertex in layers: first the source, then its neighbours, then their unvisited neighbours, and so on. It uses a queue and runs in time $O(\abs{V} + \abs{E})$. It finds every vertex reachable from the source and, for each, a path with the fewest edges, so it computes distances in unweighted graphs.