Breadth-First Search

Breadth-first search explores vertices in nondecreasing edge-count distance from a start vertex. A FIFO queue holds discovered but unprocessed vertices in layer order. Constant-time endpoint operations preserve the linear traversal bound; repeatedly using Python list.pop(0) would add element-shifting work.

from collections import deque


def bfs(graph: dict[str, list[str]], start: str):
    queue = deque([start])
    distance = {start: 0}
    parent = {start: None}
    order = []

    while queue:
        vertex = queue.popleft()
        order.append(vertex)
        for neighbor in graph.get(vertex, []):
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                parent[neighbor] = vertex
                queue.append(neighbor)
    return order, distance, parent

Discovery state doubles as the visited set. Mark a neighbor before enqueuing it so each reachable vertex enters the queue at most once.

Open full-size image

Numbers mark queue-entry order, not distance. Black edges form the discovery tree. Follow its levels from 0; changing neighbor order can change numbering within a level.

Pat Morin, Open Data Structures, Figure 12.4; cropped from the PDF. · CC BY 2.5 CA

Invariant and guarantee

When a vertex leaves the queue, its recorded distance is the minimum number of edges from the start. All earlier queue entries have distance no greater than all later entries. Parent links reconstruct one such shortest path.

The guarantee is for unweighted graphs, or graphs where every edge has equal cost. Weighted edges require algorithms such as Dijkstra or Bellman–Ford.

Cost

With adjacency lists, BFS over the reachable subgraph takes $O(V+E)$ time and $O(V)$ auxiliary space. The queue can be wide even when the graph is shallow, which is the main memory contrast with depth-first exploration.

Uses

• shortest paths by edge count;
• connected components in undirected graphs;
• bipartite testing by alternating layer colors;
• level-order traversal and bounded-radius neighborhoods.

A layer trace and path reconstruction

Use the directed adjacency lists A: [B, C], B: [D], C: [D], D: []. The queue starts [A]. Removing A enqueues [B, C], both at distance 1. Removing B gives [C, D] and assigns D distance 2, parent B. Removing C does not enqueue D again. Removing D empties the queue. Thus the order is [A, B, C, D] and one shortest path is A, B, D.

Why is first discovery final? If a shorter path to D existed, its predecessor would lie in an earlier layer. FIFO processing would already have explored that predecessor and discovered D, contradicting its first discovery now. This is the layer argument behind BFS shortest paths.

After order, distance, parent = bfs(graph, start), reconstruct a path as follows:

def reconstruct_path(parent, target):
    if target not in parent:
        return None
    path = []
    while target is not None:
        path.append(target)
        target = parent[target]
    return path[::-1]

This helper uses the shown string-vertex contract (None is only the root sentinel). An unreachable target returns None; the start returns [start]. A length-$L$ path takes $O(L)$ time and output storage; this simple reversal also uses $O(L)$ temporary storage.

Assume finite adjacency lists, no mutation, and expected constant-time hash operations. Each reachable vertex is enqueued once and each outgoing entry scanned once, proving termination and $O(V+E)$ work. Self-loops and repeated edges do not cause repeated visits. Missing keys mean no outgoing edges; bfs({}, "A") treats A as isolated. Unreachable vertices are absent from the result, not at distance zero. Input storage includes the whole graph, even unreachable parts; the returned maps and order use $O(V)$, and the queue alone may require $O(V)$ auxiliary space. Equal edge costs must be nonnegative for the minimum-edge path also to minimize cost; arbitrary weights do not satisfy this guarantee.

Run these boundary checks after the definitions above:

graph = {"A": ["A", "B", "C"], "B": ["D"], "C": ["D"], "D": [], "X": []}
order, distance, parent = bfs(graph, "A")
assert order == ["A", "B", "C", "D"]
assert distance == {"A": 0, "B": 1, "C": 1, "D": 2}
assert reconstruct_path(parent, "D") == ["A", "B", "D"]
assert reconstruct_path(parent, "A") == ["A"]
assert reconstruct_path(parent, "X") is None
assert bfs({}, "A") == (["A"], {"A": 0}, {"A": None})

Run the USF BFS animation from a chosen start vertex. Watch a vertex enter the queue when it is discovered and leave it when its neighbors are processed. Check that a second edge to an already discovered vertex does not create another queue entry.

Source

• Open Data Structures: Breadth-First Search

My reading · Opened notes are remembered in this browser.