Breadth-First Search (BFS)

Breadth-First Search explores a graph the way ripples spread on a pond. Starting from a source vertex s, it visits:

1. s itself (distance 0),
2. every neighbor of s (distance 1),
3. every still-unvisited neighbor of those (distance 2),
4. and so on until every vertex reachable from s has been seen.

The machinery that produces this layered order is a FIFO queue: we put s in, and every time we pop a vertex we push its unvisited neighbors. Because the queue is first-in-first-out, layer k is fully drained before any layer-k+1 vertex is processed.

This gives BFS a remarkable property:

The order in which BFS first visits a vertex equals its distance (in number of edges) from the source.

That is why BFS finds shortest paths in unweighted graphs.

Every BFS implementation carries three pieces of state:

• A queue Q — vertices discovered but not yet processed.
• A visited array (boolean) — has this vertex ever been enqueued? Prevents revisiting and infinite loops in graphs with cycles.
• A dist array (integer) — the BFS distance from the source. Initialized to ∞ (or -1); set to dist[u] + 1 the first time a vertex is discovered.

The invariant: a vertex is enqueued exactly once. The first time you see a vertex is the only time you see it, because BFS guarantees that first arrival is via a shortest path.

Optionally also store parent — the vertex that discovered this one — so you can reconstruct the actual path back to the source.

Run BFS from source 1 on this undirected graph, one step at a time. Step forward and backward with the ← / → arrow keys or the buttons below.

Watch the three pieces of state evolve together:

• Node colors — gray = unvisited, cyan = discovered and waiting in the queue, amber = the vertex currently being processed, green = finished.
• The queue panel — vertices enter at the back and leave from the front (FIFO), which is exactly what produces the layer-by-layer order.
• The dist[] labels — set once, the first time a vertex is discovered, and never changed again.

The cyan edges are tree edges — the edge along which each vertex was first discovered. Together they form the BFS tree, and every vertex's dist label is its shortest-path distance from the source.

Here is the one-paragraph argument. The queue is processed in FIFO order, so all vertices at distance k are popped before any vertex at distance k + 1. When a popped vertex u discovers a previously unvisited v, the new dist[v] = dist[u] + 1. If a shorter path to v existed (< dist[u] + 1), some vertex on that path would have popped first and would have visited v earlier — contradiction. So the first time we reach v is via a shortest path.

This is why BFS shows up everywhere:

• Shortest path in unweighted graphs and on grids.
• Connected components in undirected graphs — repeat BFS from each unvisited vertex.
• Bipartite check — 2-color the BFS layers; the graph is bipartite iff no edge joins two same-colored vertices.
• Level-order traversal of a tree.
• Topological sort via Kahn's algorithm uses the same queue mechanism.

The complete BFS routine plus shortest-path reconstruction from the parent[] array. Every line maps directly onto the visualization above: the while loop is the dequeue step, and the if not visited branch is the discover-and-enqueue step. The C++ tab has a ready-to-run program on the exact graph from the visualization.

Each vertex is enqueued at most once → it is dequeued at most once → its adjacency list is scanned at most once.

Sum over all vertices: each vertex contributes O(1) for enqueue/dequeue + O(deg(v)) for scanning its neighbors. The total work for scanning is Σ deg(v) = 2E for undirected (or E for directed) — every edge is inspected a constant number of times.

• Time: O(V + E).
• Space: O(V) for the queue, visited, and dist arrays.

With an adjacency list, both bounds are achieved. With an adjacency matrix, neighbor iteration is O(V) per vertex, so the running time degrades to O(V²).