Breadth-first search (BFS) explores a graph outward from a starting vertex in layers of increasing path length.

A queue stores vertices whose neighbors still need to be examined. When a vertex is discovered for the first time, it is marked and added to the queue.

In an unweighted graph, BFS discovers every reachable vertex using the minimum possible number of edges from the source. The predecessor recorded at first discovery forms a shortest-path tree.

With adjacency lists, each vertex and edge is processed only a constant number of times, giving

$$O(|V|+|E|)$$

time.

The queue is essential to the traversal order: earlier discoveries are expanded before later ones, which is what creates the layer-by-layer shortest-path property.