Exploring in rings
In the previous guide you fixed a graph in memory as either an adjacency list or a matrix, and saw that the list is the natural home for sparse graphs because it lets you sweep a vertex's neighbours in time proportional to how many there actually are. Breadth-first search, or BFS, is the first real algorithm built on top of that representation, and its idea is almost childishly simple: start at a source vertex, visit all of its neighbours, then all of their unvisited neighbours, and keep rippling outward. You explore the graph in concentric rings — everything one edge from the source, then everything two edges away, then three — never touching a far ring until the nearer one is completely done.
The whole trick that enforces this ring-by-ring order is a single data structure: a queue, first-in-first-out. You put the source in the queue; then you repeatedly take a vertex off the front, look at each of its neighbours, and for every neighbour you have never seen before, mark it visited and push it onto the back. Because the queue hands vertices back in the order they were discovered, and a vertex two edges out is only ever discovered after every vertex one edge out has already been queued, the FIFO discipline silently guarantees that you finish ring 1 entirely before ring 2 begins. No sorting, no priorities — just a plain queue doing the bookkeeping. That is BFS as a graph-exploration design tool: a controllable, total walk over everything reachable from the source.
The algorithm, step by step
- Set dist[s] = 0 for the source s, and dist[v] = infinity (meaning "not yet reached") for every other vertex. Put s in the queue and mark it visited.
- While the queue is not empty, dequeue the front vertex u.
- For each neighbour v of u (read straight off u's adjacency list): if v is unvisited, set dist[v] = dist[u] + 1, record u as v's parent, mark v visited, and enqueue v.
- When the queue empties, every vertex reachable from s carries its correct distance in dist[], and the parent pointers spell out a shortest path back to s for each one.
Let us run it on a tiny graph. Vertices a, b, c, d, e; edges a-b, a-c, b-d, c-d, d-e. Start from a. We enqueue a with dist 0. Dequeue a, see b and c: both new, so dist[b] = dist[c] = 1, enqueue both. Dequeue b, see a (visited, skip) and d (new), so dist[d] = 2, enqueue d. Dequeue c, see a (skip) and d (already visited — skip!), nothing new. Dequeue d, see e (new), dist[e] = 3. Dequeue e, no new neighbours, queue empty. Final distances: a=0, b=1, c=1, d=2, e=3 — exactly the ring each vertex sits in. Notice d was reached via b, not c, purely because b came off the queue first; the count of edges is forced, but the particular shortest path can depend on neighbour order.
What does this cost? Each vertex is enqueued at most once (the visited mark guarantees it), so the dequeue loop runs at most |V| times. And each time you dequeue a vertex you scan its entire adjacency list exactly once, so across the whole run you look at every edge a constant number of times — twice in an undirected graph, once each direction. Adding those up gives O(|V| + |E|), linear in the size of the graph. This is the same bound a plain traversal costs, and it is why the adjacency-list representation matters so much: on a matrix the neighbour scan would cost O(|V|) per vertex regardless of how few edges exist, dragging BFS up to O(|V|^2).
Why the layers really are distances
It is one thing to see the right distances pop out of the trace; it is another to know they are always right. The claim is precise: when BFS finishes, dist[v] equals the shortest path in edges from s to v — the minimum number of edges on any path from s to v — for every reachable v. The proof rests on one tidy invariant about the queue, and it is worth holding in your head because it is the entire reason BFS deserves the word "shortest."
The invariant is this: at every moment, the queue holds vertices of at most two distinct distance values, d and d+1, with all the d's sitting in front of all the d+1's. In other words the queue is always sorted by distance, in non-decreasing order. Why does FIFO keep it that way? When you dequeue a vertex u at distance d, every fresh neighbour you enqueue gets distance d+1 and goes to the back — behind any d's still waiting, and lined up neatly with the other d+1's already there. So you can never enqueue a vertex out of distance order, and you process vertices in non-decreasing distance throughout. This is exactly the ring-by-ring behaviour, now stated as something you can prove rather than just picture.
From that invariant the distance claim follows by induction. When v is first discovered, it is discovered while expanding some u with dist[u] = d, so dist[v] is set to d+1; and because we process in non-decreasing distance, no later, longer route can sneak in and overwrite it (the visited mark forbids a second assignment anyway). A short argument shows d+1 is genuinely the minimum: any path from s to v has a last vertex before v, that vertex sits at distance at least d on its own shortest path, so v cannot be closer than d+1. Honest caveat: this clean reasoning relies on every edge counting as exactly one step. The moment edges carry different weights, the queue invariant breaks — a cheap two-edge route can beat an expensive one-edge route — and BFS is simply the wrong tool, a point the next section makes sharp.
Where the promise stops: weights
BFS solves the single-source shortest path problem, but only the unweighted version of it — where "shortest" means fewest edges. The instant your edges have lengths or costs, fewest-edges and least-total-cost can disagree, and BFS happily returns the fewest-edges answer, which may be far from cheapest. Picture s connected to t two ways: a direct edge of weight 10, and a two-hop detour s-x-t of weights 1 and 1. BFS calls the direct edge the winner (one edge beats two) and reports cost 10, while the true cheapest path costs 2. BFS is not buggy here — it answered the question it actually solves, which was the wrong question for a weighted graph.
The fix is not to patch BFS but to upgrade the queue. If you replace the plain FIFO queue with a priority queue that always hands back the vertex of smallest tentative distance, you get Dijkstra's algorithm — BFS's weighted big sibling. Where BFS pulls vertices in discovery order, Dijkstra pulls them in order of cheapest known cost, which is the right generalization of "nearest ring first" once rings can have unequal thickness. And here lives one of the most important honest caveats in all of shortest paths: Dijkstra is only correct when every edge weight is non-negative. A single negative edge can make a vertex's true cheapest cost drop after Dijkstra has already finalized it, breaking the algorithm; for graphs with negative edges you need a different method (Bellman-Ford), at higher cost.
Two things BFS hands you on the side
The parent pointers BFS records along the way knit together into a BFS tree rooted at the source: a spanning tree of everything reachable, in which the unique tree path from the root to any vertex v is a genuine shortest (fewest-edges) path to v. That is a free bonus — you wanted distances, and you also got an explicit shortest path to every vertex, reconstructible by walking parent links backward from v to s. If the graph has several disconnected pieces, one BFS only reaches the source's piece; restart BFS from any still-unvisited vertex and repeat until none remain, and the number of restarts is exactly the number of connected components. Each restart's tree is that component's own BFS tree.
The second gift is bipartiteness testing. A graph is bipartite if you can two-colour its vertices so that every edge joins different colours — equivalently, if it has no odd-length cycle. BFS tests this almost for free: colour each vertex by the parity of its BFS level, source level-0 one colour, all odd levels the other, all even levels back to the first. Then make one check — does any edge connect two vertices of the same level-parity? If no edge does, the colouring is valid and the graph is bipartite. If some edge joins two same-colour vertices, that edge plus the tree paths up to their common ancestor closes an odd cycle, and an odd cycle can never be two-coloured, so the graph is provably not bipartite — and you can even hand back the offending odd cycle as a witness.
Both of these ride along inside the same single O(|V| + |E|) pass — no extra asymptotic cost, just a parity field and a colour check folded into the existing loop. That is the quiet lesson of this guide: BFS is less a single algorithm than a reusable chassis. The next guide swaps the queue for a stack (explicitly or via recursion) to get depth-first search, which trades BFS's distance guarantee for a different superpower — a rich classification of edges into tree, back, forward, and cross edges that unlocks cycle detection, topological ordering, and much of the rest of this rung.