Breadth-First Search

Level-order traversal in trees visited nodes layer by layer, and did so with a queue. The same idea works in graphs — with one difference: a graph has cycles, and the same vertex can be reached by more than one path.

Breadth-first search is a traversal that advances layer by layer according to distance from the starting vertex.

Visited Marking

In a tree, every node was reached by exactly one path; a graph gives no such guarantee. Without marking, the same vertex would enter the queue repeatedly, and if a cycle exists, the traversal would never finish.

For this reason, every graph traversal keeps a visited set. A vertex is marked when it is placed in the queue; a marked vertex is never added again.

The visited set is the only structural addition that separates graph traversals from tree traversals; everything else is the same. It matters that marking happens while adding to the queue. If it happened while removing instead, the same vertex could be added multiple times before being removed once, and the queue would grow unnecessarily.

The Algorithm

from collections import deque

def breadth_first_search(adjacency: dict[str, list[str]], start: str):
    """Traverses layer by layer; returns (visit order, distances, parents)."""
    visited = {start}
    distance = {start: 0}
    parent: dict[str, str | None] = {start: None}
    order: list[str] = []
    queue = deque([start])

    while queue:
        vertex = queue.popleft()               # first in, first out
        order.append(vertex)
        for neighbor in adjacency.get(vertex, []):
            if neighbor not in visited:
                visited.add(neighbor)          # mark while adding
                distance[neighbor] = distance[vertex] + 1
                parent[neighbor] = vertex
                queue.append(neighbor)
    return order, distance, parent


adjacency = {
    "west":   ["north", "south"],
    "north":  ["west", "center"],
    "south":  ["west", "center"],
    "center": ["north", "south", "east"],
    "east":   ["center"],
}

order, distance, parent = breadth_first_search(adjacency, "west")
print(order)          # ['west', 'north', 'south', 'center', 'east']
print(distance)       # {'west': 0, 'north': 1, 'south': 1, 'center': 2, 'east': 3}

The visit order follows the layers: first the start, then everything one edge away, then everything two edges away. The center vertex is reachable through both north and south; marking ensures only the first of these is considered.

Unweighted Shortest Path

The most important property of breadth-first search shows up here: the distances it finds are the shortest-path lengths in an unweighted graph.

The reasoning lies in the layered advance. When a vertex is reached for the first time, every vertex processed so far is at a closer or equal distance; a shorter path is therefore impossible to find later. This is a direct consequence of the queue’s first-in-first-out behavior — had a stack been used, the guarantee would disappear.

Once parent records are kept, the path itself can be reconstructed:

def build_path(parent: dict[str, str | None], target: str) -> list[str]:
    """Reconstructs the path to the target from the parent records."""
    if target not in parent:
        return []                              # unreachable
    path = []
    vertex: str | None = target
    while vertex is not None:
        path.append(vertex)
        vertex = parent[vertex]
    return list(reversed(path))


print(build_path(parent, "east"))     # ['west', 'north', 'center', 'east']
print(build_path(parent, "none"))     # []

The path is traced backward from the target and then reversed. The same technique is also used in the weighted shortest-path algorithms taken up in the next course.

Once weight enters the picture, breadth-first search is no longer enough: a few heavy edges can cost more than many light ones. That case requires algorithms that use a priority queue instead of a plain queue; the heap from the trees topic is one of the basic building blocks of graph algorithms for this reason.

The same technique can also be applied bidirectionally in searches where the target is also known: two searches are started — one from the start, one from the target — and the path is found once they meet. Because each search advances only to half the depth, the number of vertices visited drops noticeably; the gain is large in graphs with a high branching factor.

Cost

Each vertex enters the queue at most once, and each edge is examined at most twice (once from each end, in an undirected graph). With an adjacency list the total cost is:

$$O(\lvert V \rvert + \lvert E \rvert)$$

The memory cost is the largest number of vertices that can be in the queue at once — the width of the widest layer. In wide, shallow graphs this number can be large; it is the same observation made for level-order traversal in trees.

Multi-Source Search

Breadth-first search is not limited to a single starting vertex. If multiple vertices are placed in the queue from the start, the traversal spreads from all sources at once, and the distance found for each vertex is its distance to the nearest source.

def multi_source(adjacency: dict[str, list[str]], sources: list[str]) -> dict[str, int]:
    """Returns, for each vertex, its distance to the nearest source."""
    distance = {s: 0 for s in sources}
    queue = deque(sources)
    while queue:
        vertex = queue.popleft()
        for neighbor in adjacency.get(vertex, []):
            if neighbor not in distance:
                distance[neighbor] = distance[vertex] + 1
                queue.append(neighbor)
    return distance


print(multi_source(adjacency, ["west", "east"]))
# {'west': 0, 'east': 0, 'north': 1, 'south': 1, 'center': 1}

In the single-source search, the distance of the center vertex was two; with two sources it becomes one, because it is a neighbor of east.

This pattern solves problems such as “each cell’s distance to the nearest water source” or “each vertex’s latency to the nearest server” in a single pass, without running a separate search for each source. Doing the same work with one search per source would multiply the cost by the number of sources.

Uses

Fewest-step solution. When a puzzle’s states are vertices and moves are edges, breadth-first search finds the solution with the fewest moves.

Connected components. Starting a search from every unvisited vertex splits the graph into its components. The question from the disjoint-sets lesson is answered here by traversal; the difference is that the structure there works while edges arrive as a stream.

Bipartiteness test. Layers are colored alternately with two colors; if an edge is found between two vertices in the same layer, the graph is not bipartite.

Spread patterns. How far and in how many steps information reaches through a network, an effect spreads through a community, or a fault propagates through a system.

Web crawling. Crawlers that follow links use breadth-first search to traverse by distance from a starting address.

One last caution: the shortest-path guarantee of breadth-first search rests on treating every edge as equally costly. The moment weights are added, the guarantee disappears and a priority queue is needed instead of a plain queue; this explains the role of the heap from the trees topic in graph algorithms. If only part of the weights differ — for example, some edges cost zero and others cost one — an intermediate solution using a double-ended queue can also be used.

Summary

• Breadth-first search advances layer by layer by distance from the start, using a queue.
• Because the same vertex can be reached by more than one path in a graph, visited marking is required; marking happens while adding to the queue.
• The distances found are the shortest-path lengths in an unweighted graph; the guarantee comes from the queue’s first-in-first-out behavior.
• Once parent records are kept, the path itself is reconstructed by tracing backward.
• Cost is $O(V + E)$ with an adjacency list; memory depends on the widest layer.
• Breadth-first search is not enough for weighted graphs; algorithms using a priority queue are needed.

Next Step

Breadth-first search prioritizes width: everything nearby is visited before anything farther. The opposite strategy is to follow a single path to its end and only then turn back. The next lesson takes up that strategy and the different family of problems it solves.