---
title: 'Breadth-First Search'
source: 'https://academia.sh/en/courses/data-structures/breadth-first-search'
course: 'Data Structures'
language: en
updated: '2026-08-17T18:07:52+00:00'
license: 'CC BY-SA 4.0'
---

# Breadth-First Search

Layer-by-layer traversal with a queue, visited marking, unweighted shortest path, and path reconstruction.

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

```python
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:

```python
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.

```python
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.