Breadth-First Search

5 min read#networks#algorithms#traversal

Explore a graph in concentric layers from a source — the simplest way to find shortest paths in an unweighted graph.

Contents

Breadth-First Search

Breadth-first search (BFS) explores a graph the way ripples spread on a pond. Starting from a source node, it first visits every immediate neighbor, then every node two steps away, then three — fanning outward one layer at a time. Because it never moves to distance d+1 until it has exhausted everything at distance d, the moment BFS first reaches a node it has reached it by the fewest possible edges.

That single property makes BFS the canonical tool for shortest paths in an unweighted Graph: the layer in which a node appears is its distance from the source.

The algorithm: a queue and a wavefront

BFS is built on a queue — a first-in, first-out line. You enqueue the source, then repeatedly take the front node, mark its unvisited neighbors as discovered, record their distance, and enqueue them. Because nodes leave the queue in the order they entered, the search expands strictly by distance.

Watch the wavefront spread

On the grid below, BFS starts from a single cell and floods outward. Each cell is colored by the layer in which it is discovered — its graph distance from the source. The boundary between explored and unexplored is the frontier, and it is exactly the queue's contents at that instant. Notice how the colored bands form a diamond: on a 4-neighbor grid, graph distance is Manhattan distance, not straight-line distance.

BFS flooding outward from a source cell. Color encodes distance (the BFS layer). The advancing edge is the frontier — the queue made visible. It re-runs from a new random source each pass.

When breadth wins

Because BFS settles each node by distance, it is the right choice whenever every edge counts the same: the fewest hops between two people in a social graph, the minimum moves in a puzzle, the nearest exit in a maze. Its sibling Depth-First Search instead dives as deep as it can before backing up — better for detecting cycles and ordering dependencies, but with no shortest-path guarantee. And the moment edges carry unequal weights, layer-by-layer breadth is no longer enough: you need the weighted generalization, Dijkstra's Algorithm, which is BFS with a priority queue in place of a plain one.

See also