Elijah's Notes

Breadth First Search Pattern

3 min read

Purpose

BFS shows up constantly in graph problems. This note pins down the one property that makes it useful, the level-by-level visit order, and lists the problems that property solves.

Core idea

BFS explores vertices in order of the length of their shortest path from the starting vertex. Any time you have an unweighted graph and need the shortest path between two vertices, start with BFS.

Weights break the guarantee

BFS orders vertices by edge count, not by path weight. On a weighted graph the first path BFS finds can carry more total weight than a path with more edges, so use Dijkstra’s algorithm for weighted shortest paths.

Intuition

BFS runs on a queue. The start vertex goes in first, and each dequeued vertex enqueues its undiscovered neighbors. Every vertex at distance enters the queue before any vertex at distance , and so on, so the traversal processes the graph one distance ring at a time. The first time BFS discovers a vertex, it got there through a shortest path.

Level sets

You can describe the traversal as producing level-wise sets of vertices. Let be the start vertex and define

Each level is exactly the set of vertices at distance from . A quick induction shows why. Suppose every vertex in levels through sits at distance equal to its level index. A vertex has a neighbor in , so its distance is at most . Its distance can’t be smaller than either, because a vertex at distance has a neighbor at distance , and that neighbor’s level would have pulled into .

On a small graph the levels form distance rings around . The edge inside is exactly the kind a bipartiteness check flags:

flowchart LR
    subgraph L0
        s((s))
    end
    subgraph L1
        a((a))
        b((b))
    end
    subgraph L2
        c((c))
        d((d))
    end
    s --- a
    s --- b
    a --- b
    a --- c
    b --- c
    b --- d

What it solves

  • Shortest paths in unweighted graphs.
  • Connected components, by running BFS from every unvisited vertex.
  • Bipartiteness checks, since an edge between two vertices in the same level implies an odd cycle.

Graph View