Algorithms and data structures · Introductory

Breadth-first search: visit vertices by edge distance

Use a queue and discovery markers to find shortest paths by number of edges in an unweighted graph.

Ask Logeia about this articleTry the three questionsReview your answers

Updated

On this page
  1. Process vertices in layers of equal distance
  2. Trace the queue and a recovered path
  3. Mark discovery when enqueuing
  4. Check what “shortest” means in the problem
  5. Reconstruct a path from predecessor links
  6. Handle several sources and unreachable vertices
  7. Ask Logeia about this articleCheck your understanding

Process vertices in layers of equal distance

Breadth-first search, or BFS, explores vertices at distance zero, then one edge, then two edges, and so on from a starting vertex. Place the start in a queue, remove a vertex from the front, and append its undiscovered neighbors at the back. This first-in, first-out discipline processes nearer layers before farther ones. When all edges have equal cost, the distance assigned on first discovery is the shortest number of edges from the start. The guarantee concerns edge count, not arbitrary numerical weights attached to edges.

Trace the queue and a recovered path

Take edges A → B, A → C, B → D, and C → D. Starting at A and examining B before C changes the queue from [A] to [B, C]. Removing B discovers D and leaves [C, D]. When C examines D, D is already discovered and is not added again. Its distance is two. Recording B as D’s predecessor allows the path A → B → D to be reconstructed. A different neighbor order can choose another equally short path without changing the minimum edge count.

ActionRemaining queueNew distance
Process A[B,C]B=1, C=1
Process B[C,D]D=2
Process C[D]D already discovered
Process D[]No change

Mark discovery when enqueuing

A common implementation marks a vertex as discovered when placing it in the queue. Waiting until removal can allow several predecessors to enqueue the same vertex repeatedly. With adjacency lists, each vertex is removed once and every relevant edge is inspected a constant number of times, giving O(V + E) time for a whole-graph bound. Distances, predecessors, and the queue require O(V) auxiliary storage. A representation using an adjacency matrix can change the neighbor-scanning cost. The complexity statement must name the representation, not just the traversal algorithm.

python
from collections import deque

def distances(graph, start):
    distance = {start: 0}
    queue = deque([start])
    while queue:
        vertex = queue.popleft()
        for neighbor in graph.get(vertex, []):
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    return distance

Check what “shortest” means in the problem

Suppose A → D costs 100 while A → B and B → D each cost one. BFS discovers the one-edge route first, although the two-edge route has lower total weight. For weighted costs, choose an algorithm whose assumptions match those weights, such as Dijkstra’s method for nonnegative weights. Unreachable vertices remain undiscovered and need an explicit sentinel distinct from distance zero. Initializing several starting vertices at zero distance is a useful extension that computes distance to the nearest start. State that initialization contract when interpreting the result.

Reconstruct a path from predecessor links

If a path is needed, record the predecessor when each vertex is first discovered. If D points back to B and B to A, following predecessors yields D,B,A; reverse that sequence to obtain A,B,D. Distance two alone does not identify the intermediate vertex. Check reachability before reconstruction because an unreachable target has no discovered predecessor. When several shortest paths exist, this representation returns one determined by neighbor order. Enumerating every shortest path requires a different predecessor representation and accounting for the potentially large number of outputs. The distance guarantee and the particular selected path are separate parts of the interface.

Python
from collections import deque

def bfs(graph, start):
    distance = {start: 0}
    parent = {start: None}
    queue = deque([start])
    while queue:
        u = queue.popleft()
        for v in graph.get(u, []):
            if v not in distance:
                distance[v] = distance[u] + 1
                parent[v] = u
                queue.append(v)
    return distance, parent

Handle several sources and unreachable vertices

To compute distance to the nearest of several sources, initialize each distinct source with distance zero and enqueue all of them before starting the ordinary traversal. Vertices reached later receive their minimum edge count from any source. A vertex unreachable from every source must remain unreachable rather than receiving zero. An adjacency-matrix implementation scanning every possible neighbor does not inherit the adjacency-list O(V+E) operation count unchanged. Memory also depends on the graph’s breadth: the queue may contain a wide layer even when paths are short. Test converging edges, cycles and disconnected vertices, not only a simple chain.

Reading and practice are recorded separately in this browser, for each language.

Learn this in order

Build your CS foundations · STEP 11

Choose a learning path