Skip to main content

Breadth-First Search

Breadth-first search explores vertices in nondecreasing distance from a start vertex. A FIFO queue holds the next discovered layer.

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.

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)O(V+E) time and O(V)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.

Source​