Breadth-First Search, in depth: the queue invariant, a traced example, CSR graphs and direction-optimising BFS

The algorithm and its cost

BFS keeps three things: a FIFO queue of discovered but unprocessed vertices, a distance (or visited marker) per vertex, and optionally a parent per vertex. Start by setting the source's distance to 0 and enqueueing it. Then repeat: dequeue a vertex u; for each neighbour v not yet discovered, set dist[v] = dist[u] + 1, record parent[v] = u, and enqueue v.

The crucial detail is when a vertex counts as visited: at discovery, when it is enqueued, not when it is dequeued. Marking at dequeue lets the same vertex be enqueued once per incoming edge, so the queue can grow to O(E) entries, work is duplicated, and with some update rules the stored distance can be overwritten by a later, longer one.

Each vertex is enqueued and dequeued at most once, and each adjacency list is scanned once when its vertex is dequeued, so the running time is O(V + E) with adjacency lists. With an adjacency matrix, scanning a row costs O(V) whatever the degree, so BFS becomes O(V²), which is only acceptable for small dense graphs.

Why the first discovery is a shortest path

Why does the first discovery give a shortest distance? The argument rests on one invariant you can assert in tests: at every moment the queue holds vertices in non-decreasing distance order, and the first and last differ by at most 1. Initially the queue is just the source. When we dequeue u with distance d, every vertex still in the queue has distance d or d + 1, and every vertex we append gets distance d + 1, so the order and the spread are preserved.

From the invariant, vertices are dequeued in non-decreasing distance order: all of layer d, then all of layer d + 1. Now suppose some vertex v were assigned a distance larger than its true distance δ(v); take the one with the smallest δ. Its predecessor w on a true shortest path has δ(w) = δ(v) − 1 and, by minimality, was assigned that correctly. When w was dequeued, v was either undiscovered, in which case it gets δ(w) + 1 = δ(v), or already discovered by a vertex dequeued no later than w, which gives a distance no larger. Either way, contradiction.

A corollary is useful for debugging: in an undirected graph every edge connects vertices whose BFS distances differ by at most 1. An edge with a gap of 2 or more in your output means the traversal is wrong.

Worked example: tracing the queue

Take the undirected graph with edges 0–1, 0–2, 1–3, 2–3, 2–4, 3–5, 4–5, 5–6, 4–7, neighbours in ascending order, and start at 0.

Final distances are [0, 1, 1, 2, 2, 3, 4, 3] and parents [-1, 0, 0, 1, 2, 3, 5, 4]. Following parents back from 6 gives the path 0, 1, 3, 5, 6. Notice that edge 2–3 was seen twice but 3 entered the queue once, and that the queue never held more than two adjacent layers.

A reference implementation

A reference implementation over adjacency lists with integer vertex ids. It returns distances and parents; -1 means unreachable.

from collections import deque

def bfs(adj, source):
    n = len(adj)
    dist = [-1] * n
    parent = [-1] * n
    dist[source] = 0
    q = deque([source])
    while q:
        u = q.popleft()
        for v in adj[u]:
            if dist[v] == -1:                  # mark on discovery, not on dequeue
                dist[v] = dist[u] + 1
                parent[v] = u
                q.append(v)
    return dist, parent

def path_to(parent, dist, target):
    if dist[target] == -1:
        return None
    path = []
    while target != -1:
        path.append(target)
        target = parent[target]
    return path[::-1]

Use collections.deque or an array with a head index; list.pop(0) shifts the whole list and turns BFS quadratic. For a single target you may stop as soon as the target is discovered, since its distance is already final. For all components, wrap the call in a loop over vertices and start a new BFS from each one still at -1. Multi-source BFS just seeds the queue with several sources at distance 0.

Compressed sparse row and memory

Lists of Python lists, or vectors of vectors in C++, scatter adjacency across the heap. Large-graph code uses compressed sparse row (CSR): an offsets array of length V + 1 and a targets array holding all neighbour ids back to back, so the neighbours of u are targets[offsets[u]:offsets[u+1]].

def to_csr(n, edges):                       # undirected: store each edge in both directions
    offsets = [0] * (n + 1)
    for a, b in edges:
        offsets[a + 1] += 1
        offsets[b + 1] += 1
    for i in range(n):
        offsets[i + 1] += offsets[i]
    targets = [0] * offsets[n]
    fill = offsets[:-1]
    for a, b in edges:
        targets[fill[a]] = b; fill[a] += 1
        targets[fill[b]] = a; fill[b] += 1
    return offsets, targets

Sizing is simple arithmetic. An undirected graph with 100 million vertices and 1 billion edges stores 2 billion targets; with 32-bit ids that is 8 GB. Offsets need 64-bit entries once the edge count exceeds what a 32-bit index can address, adding 800 MB. The distance array is 400 MB at 32 bits, and a visited bitmap only 12.5 MB.

Speed is dominated by memory, not arithmetic. Scanning a neighbour range is sequential and cache friendly; checking dist[v] for each neighbour is a random access, usually a cache miss on a large graph. That is why a compact visited bitmap that fits in cache matters, and why relabelling vertices so neighbours have nearby ids (for example by BFS or degree order) can speed traversal up noticeably.

Level-synchronous and direction-optimising BFS

Processing one whole layer at a time, a level-synchronous BFS, is the form used in parallel and distributed implementations: the current frontier is a list or bitmap, the next frontier is built from it, and threads split the frontier. It is also what made a major optimisation possible.

In top-down steps each frontier vertex scans its edges looking for undiscovered neighbours. On low-diameter graphs such as social networks the middle frontiers contain a large fraction of all vertices, and most of those edge checks hit vertices already discovered. Beamer, Asanović and Patterson (2012) proposed bottom-up steps for those layers: each undiscovered vertex scans its own neighbours and stops at the first one in the frontier. Their direction-optimising BFS switches to bottom-up when the frontier's outgoing edges exceed the unexplored edges divided by a parameter α, and back to top-down when the frontier shrinks below V divided by β (the paper tuned α = 14 and β = 24; treat them as starting points for your own graphs).

def bfs_levels(offsets, targets, source, alpha=14, beta=24):
    n = len(offsets) - 1
    dist = [-1] * n
    dist[source] = 0
    frontier, level, mode = [source], 0, "top-down"
    unexplored = len(targets)
    while frontier:
        f_edges = sum(offsets[u + 1] - offsets[u] for u in frontier)
        if mode == "top-down" and f_edges > unexplored / alpha:
            mode = "bottom-up"
        elif mode == "bottom-up" and len(frontier) < n / beta:
            mode = "top-down"
        nxt = []
        if mode == "top-down":
            for u in frontier:
                for v in targets[offsets[u]:offsets[u + 1]]:
                    if dist[v] == -1:
                        dist[v] = level + 1
                        nxt.append(v)
        else:
            for v in range(n):
                if dist[v] == -1:
                    for u in targets[offsets[v]:offsets[v + 1]]:
                        if dist[u] == level:   # a parent in the current frontier
                            dist[v] = level + 1
                            nxt.append(v)
                            break
        unexplored -= f_edges
        frontier, level = nxt, level + 1
    return dist

Both modes produce identical distances; only the work differs. Bottom-up needs the reverse edges, which an undirected CSR already has. BFS is also the kernel of the Graph500 benchmark, which reports traversed edges per second, so these optimisations are well studied on real hardware.

BFS inside real systems

BFS shows up in places that do not call it BFS. Cheney's copying garbage collector is a BFS over the object graph: objects copied into to-space form the queue, and a scan pointer chasing the allocation pointer is the dequeue, so no extra queue memory is needed. Web crawlers run BFS with politeness limits per host. Build systems and package managers use it to find everything affected by a change within k hops. Network broadcast and flooding protocols are distributed BFS, and "degrees of separation" features are bidirectional BFS on a social graph.

The shared engineering concerns are bounding memory (the frontier of a low-diameter graph can be most of the graph), deciding the visited structure (array, bitmap, or hash set for sparse ids), and making the traversal resumable when it runs for hours.

Failure modes

• Marking visited at dequeue. Duplicate queue entries, O(E) memory, wasted work.
• Using BFS on weighted edges. Fewest edges is not cheapest. Use 0-1 BFS for weights 0 and 1, Dijkstra for non-negative weights.
• Quadratic dequeue. list.pop(0) or array shifting turns O(V + E) into O(V²).
• Forgetting disconnected parts. One BFS reaches one component; distances of -1 are not zeros.
• Huge hashed states. Visited sets of tuples or strings can cost tens of bytes per entry; map vertices to dense integers when you can.
• Unbounded frontiers in services. A k-hop query on a hub vertex can touch millions of nodes; cap depth, frontier size or time, and return partial results explicitly.

What to do next

1. Implement bfs and path_to, and run them on the worked example to reproduce the table.
2. Add a test asserting that every edge joins vertices whose distances differ by at most 1.
3. Convert one of your graphs to CSR and measure memory before and after.
4. Time top-down against direction-optimising BFS on a low-diameter graph.
5. Audit any production traversal for depth, frontier and time limits.

Related reading on this site: BFS and DFS compared, BFS on implicit state spaces, 0-1 BFS for two edge weights, multi-source BFS, and Dijkstra's algorithm for general non-negative weights.