1. Breadth-First Search

Breadth-first search (BFS) is one of the two fundamental graph traversal strategies, the other being depth-first search. Starting from a source vertex \(s\), BFS explores all vertices at distance 1 (direct neighbours), then all at distance 2, and so on in expanding concentric shells, using a FIFO queue to maintain the exploration frontier. This layer-by-layer order guarantees that BFS finds the shortest path (minimum number of edges) from \(s\) to every reachable vertex in an unweighted graph ¹².

BFS also serves as the foundation for more sophisticated algorithms: Dijkstra's algorithm replaces the FIFO queue with a priority queue, and the A* algorithm adds a heuristic. Edmonds–Karp maximum flow uses BFS to find augmenting paths.

1.1 Problem Statement

Given a graph \(G = (V, E)\) and a source vertex \(s \in V\), compute:

1. The shortest-path distance \(d[v]\) from \(s\) to every vertex \(v\) reachable from \(s\).
2. A shortest-path tree rooted at \(s\) via predecessor pointers \(\pi[v]\).

where \(|P|\) denotes the number of edges in path \(P\).

1.2 The Algorithm

BFS(G, s):
  for each vertex u ∈ V \ {s}:
    color[u] = WHITE;  d[u] = ∞;  π[u] = NIL
  color[s] = GRAY;  d[s] = 0;  π[s] = NIL
  Q = empty queue
  ENQUEUE(Q, s)
  while Q ≠ ∅:
    u = DEQUEUE(Q)
    for each v ∈ Adj[u]:
      if color[v] = WHITE:
        color[v] = GRAY
        d[v] = d[u] + 1
        π[v] = u
        ENQUEUE(Q, v)
    color[u] = BLACK

1.2.1 Correctness: Shortest-Path Guarantee

BFS produces correct shortest-path distances. The key invariant on the queue \(Q\) at any point: if the queue contains vertices \(v_1, v_2, \ldots, v_r\) (in FIFO order), then

That is, the queue contains at most two consecutive distance layers. This ensures vertices are settled in non-decreasing distance order, so the first time BFS reaches \(v\), it does so via a shortest path ¹.

Proof sketch: by induction on \(d[v]\). When \(v\) is first enqueued, it is enqueued from some \(u\) with \(d[u] = d[v] - 1\). By induction \(d[u]\) is correct, so \(d[v] = d[u] + 1\) equals the true shortest-path distance.

1.3 Complexity

Space: \(O(V)\) for the queue, colour, distance, and predecessor arrays.

1.4 Properties

• Completeness: BFS visits every vertex reachable from \(s\). It is complete on all finite, connected graphs and finds all reachable vertices in any finite graph.
• Optimality: BFS finds shortest paths measured by edge count. For weighted graphs, use Dijkstra or Uniform-Cost Search.
• Tree structure: the predecessor pointers \(\pi\) define a BFS tree (also called the shortest-path tree). The unique path from \(s\) to \(v\) in this tree is a shortest path in \(G\).

1.5 Bipartiteness Testing

BFS can test whether \(G\) is bipartite (2-colourable) in \(O(V + E)\): colour \(s\) white, colour all neighbours black, all their neighbours white, and so on. If a conflict arises — an edge between two vertices of the same colour — then an odd-length cycle exists and \(G\) is not bipartite. Otherwise, the colouring witnesses bipartiteness ¹.

1.6 Variants

1.6.1 Multi-Source BFS

If several sources \(S \subseteq V\) are given, initialise all with \(d[s] = 0\) and enqueue all simultaneously before the main loop. This computes shortest distances from the nearest source to every vertex in \(O(V + E)\) — useful for problems like "nearest fire station" or "nearest safe cell" on a grid.

1.6.2 Bidirectional BFS

Run BFS simultaneously from \(s\) and the goal \(g\), alternating frontier expansions. Stop when the two frontiers meet. In a graph with branching factor \(b\) and shortest path of length \(d\), standard BFS visits \(O(b^d)\) nodes while bidirectional BFS visits \(O(b^{d/2})\) — exponentially fewer. Used in social-network distance queries and some route planners.

1.6.3 0-1 BFS

On graphs where edges have weight 0 or 1, replace the FIFO queue with a deque (double-ended queue): edges of weight 0 push to the front; edges of weight 1 push to the back. This computes shortest paths in \(O(V + E)\) without a priority queue, unlike Dijkstra.

1.7 Applications

• Shortest paths in unweighted graphs (road networks with uniform edge costs, word ladder)
• Connected components of undirected graphs
• Bipartiteness testing
• Web crawling (visit all pages within \(k\) hops)
• Social network diameter estimation
• Edmonds–Karp maximum flow (BFS augmenting paths)
• Level-order traversal of trees

1.8 Limitations

• Memory: BFS stores the entire frontier in the queue. In graphs with large branching factor \(b\) and goal at depth \(d\), the queue may contain \(O(b^d)\) nodes, making it impractical for deep goals. Iterative deepening achieves the same correctness with \(O(bd)\) memory.
• Unweighted only: for weighted graphs, BFS ignores edge costs and may return a path that minimises hops but not total weight. Use Dijkstra for weighted shortest paths.

1.9 Interactive Demo

The canvas below shows BFS on a 7×7 grid. The source is the top-left cell; the goal is the bottom-right cell. Walls are drawn as dark cells. BFS expands layer by layer, colouring each layer a slightly deeper shade.