Breadth-First Search

Explore a graph level by level using a queue. Finds shortest paths in unweighted graphs.

Level: intermediate

What is it?

Breadth-first search (BFS) visits a start vertex, then all its neighbors, then their unvisited neighbors, and so on, expanding in rings of increasing distance. A queue holds the frontier, and a visited set prevents revisiting. Because vertices are discovered in order of distance, BFS finds the shortest path (fewest edges) in an unweighted graph.

Why does it matter?

Shortest hops, minimum moves, degrees of separation, flood fill, and level-order tree traversal are all BFS. It is the simplest correct answer to 'what is the fewest steps from A to B?'.

Mental model

A ripple in a pond. Drop a stone at the start and the wave reaches everything one step away, then everything two steps away. The first time the ripple touches a place is the shortest way to get there.

How it works

Queue of the frontier; enqueue neighbors when first seen; dequeue to expand.
Mark visited when you enqueue (not when you dequeue) so a vertex is queued at most once.
Distance from the start: dist[next] = dist[node] + 1 gives the fewest edges.
Time O(V + E); memory O(V) for the queue and visited set (the widest level).
Works for grids too: cells are vertices, four or eight neighbors are edges.
Not correct for weighted shortest paths; use Dijkstra there.

Steps

Enqueue the start and mark it
Dequeue a vertex
Visit its unvisited neighbors
Enqueue and record their distance
Repeat until the queue is empty

Code example: Distances from a start vertex

from collections import deque

def bfs(graph, start):
    dist, q = {start: 0}, deque([start])
    while q:
        node = q.popleft()
        for nxt in graph[node]:
            if nxt not in dist:
                dist[nxt] = dist[node] + 1
                q.append(nxt)
    return dist

g = {"A": ["B", "C"], "B": ["D"], "C": ["D"], "D": []}
print(bfs(g, "A"))   # {'A': 0, 'B': 1, 'C': 1, 'D': 2}

Complexity and trade-offs

Time: O(V + E)

Space: O(V)

Trade-offs

Guarantees the fewest edges to every reachable vertex
The queue can hold a whole level at once, which is large for wide graphs
Ignores edge weights

Real-world usage

Shortest path in unweighted graphs and grids
Web crawlers and social-network distance
Level-order tree traversal and flood fill

Common mistakes

Marking visited on dequeue, so the same vertex is queued many times.
Using BFS distances as if edges had weights.
Forgetting disconnected components when you need to reach every vertex.

Interview questions

Why does BFS find shortest paths in an unweighted graph?

It visits vertices in nondecreasing order of distance from the start, so the first time a vertex is reached is by a path with the fewest edges.

BFS or DFS to find a path?

Either finds a path if one exists. BFS finds one with the fewest edges but uses memory proportional to the widest level; DFS uses memory proportional to depth and is simpler for exploring all possibilities or detecting cycles.

What is the complexity of BFS?

O(V + E) time, since each vertex is enqueued once and each edge is examined once, and O(V) space for the queue and visited set.