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.
| Action | Remaining queue | New 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.
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 distanceCheck 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.
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, parentHandle 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.