Breadth-First Search (BFS)

How does a network know who your 2nd-degree connections are? It explores in waves: first everyone one step away, then two, then three. That is breadth-first search, the base of Dijkstra’s and Prim’s algorithms.

★ Lecture: Graph_BFS · Zaza Gamezardashvili▶ video intermediate⏱ 20 min read

←Builds on

3Queue (FIFO) & DequeBFS is a queue put to work: the FIFO order is what makes the wave.6Graph RepresentationsBFS walks the adjacency list of each vertex it takes out of the queue.5Trees: Concepts, Properties, TraversalsOn a tree BFS is the level order traversal; on a graph it adds a visited array.

Leads to→

6Cycles, Topological Sort, Bipartite CheckThe bipartite check colours vertices layer by layer, following BFS's waves.6Tree Diameter & CenterThe diameter takes two BFS runs: farthest from any vertex, then farthest from that one.8Dijkstra's AlgorithmDijkstra is BFS whose wave moves by distance instead of by edge count.

1Learn 2Watch 3Play 4Check 5Practice

Learn

The idea, the mechanics and the cost.

01The problem and the wave

Given an unweighted graph (every edge counts as 1) and a source vertex s, find the distance, meaning the number of edges, from s to every reachable vertex. BFS works on directed and undirected graphs alike, and while it runs it builds the BFS tree rooted at s, in which the path from s to each vertex is one of the shortest.

The lecture calls BFS a wave algorithm: it first finds all vertices one edge away from s, then all vertices two edges away, and so on, like a ripple spreading over water. On the lecture’s graph with s = 4: first 5, 2 and 3; then 7, 1, 6 and 8; finally 9.

Because the wave reaches nearer vertices first, a distance found by BFS is final: it is already the shortest and never improves on later steps.

The lecture’s graph, coloured by distance from the source 4.

02Bookkeeping: colours, queue, d[], p[], used[]

To keep track, BFS paints the vertices in three colours:

white: not discovered yet (at the start, all of them);
gray: discovered and waiting in the queue;
black: all of its neighbours have been discovered.

Invariant: a black vertex never has a white neighbour, so the gray vertices form the border between the known and the unknown part of the graph.

The waiting room is a FIFO queue (first in, first out): always take the oldest vertex. That is exactly what makes the wave, because every vertex at distance x leaves the queue before any vertex at distance x + 1. The lecture’s code keeps three arrays:

d[v]: the distance from s;
p[v]: the parent of v in the BFS tree (nil, that is −1, for s);
used[v]: whether v has been discovered (gray or black).

The queue after iteration 3: distances never decrease from front to back.

03Step by step on the lecture’s graph

The loop: take v from the front; for each neighbour to that is not used, mark it, set d[to] = d[v] + 1, p[to] = v and push it to the back. Then v turns black.

On the lecture’s graph with s = 4:

init: queue [4], d[4] = 0, p[4] = nil;
iteration 1: pop 4, discover 5, 2, 3 at distance 1 → [5, 2, 3];
iteration 2: pop 5, discover 7 and 1 at distance 2 → [2, 3, 7, 1];
iteration 3: pop 2, discover 6 → [3, 7, 1, 6];
iteration 4: pop 3, discover 8 → [7, 1, 6, 8];
iteration 5: pop 7, discover 9 at distance 3 → [1, 6, 8, 9];
the remaining iterations pop 1, 6, 8 and 9 and find nothing new.

Final tables for vertices 1…9: d = 2, 1, 1, 0, 1, 2, 2, 2, 3 and p = 5, 4, 4, nil, 4, 2, 5, 3, 7.

Iteration 3: vertex 2 was processed and discovered 6.

04The BFS tree, and why it is correct

Every vertex enters the queue once, so it gets exactly one parent: the edges (p[v], v) form the BFS tree. Edge 1–7 is not in it: 1 was discovered before 7 was popped. To print a shortest path to t, follow the parents back from t and reverse: for 9 that is 9 → 7 → 5 → 4, reversed 4 → 5 → 7 → 9, three edges = d[9].

Why are the distances shortest? The lecture proves it in two steps:

Lemma: the distances of the vertices in the queue never decrease and differ by at most 1 (in iteration 3 the queue 3, 7, 1, 6 has d = 1, 2, 2, 2). By induction: popping v at distance x appends its new neighbours at x + 1 to the back.
Theorem: suppose some d[u] were wrong; take the nearest such u, with BFS parent v and predecessor w on a true shortest path. Then d[w] < d[v], so by the lemma w left the queue before v and would have discovered u first. Contradiction.

05Cost, and where BFS shows up

Each vertex is pushed and popped once: O(V). Each adjacency list is scanned once, when its vertex is popped, and together the lists hold E entries (2E in an undirected graph): O(E). Initialization is O(V). Total O(V + E), linear in the size of the graph.

The lecture lists the classic applications:

shortest paths from one vertex to all others in an unweighted graph;
connected components: restart BFS from every vertex still unmarked, one run per component;
the fewest moves in a game or puzzle whose states are vertices, such as escaping a maze;
0-1 BFS for edge weights 0 or 1: push to the front of a deque after a 0-edge, to the back after a 1-edge;
the shortest cycle in a directed graph; all vertices on some shortest a→b path (BFS from both ends and check dA[v] + dB[v] = dA[b]); the shortest path of even length, using (vertex, parity) states.

A maze like the one on the lecture’s last slide: the first touch of the exit gives the shortest route.

The lecture's C++C++

Slide 18: a vertex is marked used the moment it enters the queue, gets d[to] = d[v] + 1 and remembers its parent in p[to], which the second half follows backwards to rebuild the path. In that second half `to` is no longer the loop variable: it stands for the target vertex whose path you want, so declare and read it before that part.

vector < vector<int> > g; // გრაფი
int n, s; // n - წვეროების რაოდენობა, s - საწყისი წვერო (წვეროები გადანომრილია ნულიდან)
// გრაფის კითხვა
...
queue<int> q;
q.push (s);
vector<bool> used (n);
vector<int> d(n), p(n); // d[n] - ვექტორი მანძილებისთვის, p[n] - მშობლების ვექტორი
used[s] = true;        p[s] = -1;
while (!q.empty()) {
    int v = q.front();    q.pop();
    for (size_t i=0; i<g[v].size(); ++i) {
        int to = g[v][i];
        if (!used[to]) {
            used[to] = true;
            q.push (to);
            d[to] = d[v] + 1;
            p[to] = v;
        }
    }
}
// გზის აღდგენა
if (!used[to]) cout << "No path!";
else {
    vector<int> path;
    for (int v=to; v!=-1; v=p[v])
        path.push_back (v);
    reverse (path.begin(), path.end());
    cout << "Path: ";
    for (size_t i=0; i<path.size(); ++i)
        cout << path[i] + 1 << " ";
}

Cost at a glance

TimeO(V + E)

Memory (queue, d, p, used)O(V)

Rebuild a path from p[]O(path length)

Remember

A FIFO queue makes BFS explore in waves, level by level away from the source.
In an unweighted graph the first discovery of a vertex gives its shortest distance; p[] stores the BFS tree for rebuilding paths.
Every vertex and every edge is handled once, so BFS runs in O(V + E).

Watch

The lecture as a narrated explainer video.

▶

Watch the lecture, animated

The video follows the lecture slide by slide: the same example, the same notation. Use it before or after playing with the visualizer.

▶ Open the video page ▣ Open as presentation

Play

Step through the algorithm, then try it on your own input.

👀 What to watch: Keep your eyes on the queue: vertices leave from the left in the order they were found, and their d values never decrease. Then pick another source vertex and compare the BFS trees.

Interactive visualizerfocus here, then space ← →

Graph (source: 4)

white: undiscoveredgray: in queueblack: finishedBFS tree edge

Queue (FIFO)

State

v	1	2	3	4	5	6	7	8	9
d[] dist	∞	∞	∞	0	∞	∞	∞	∞	∞
p[] parent	∞	∞	∞	nil	∞	∞	∞	∞	∞
used[]	0	0	0	1	0	0	0	0	0

Start from source vertex 4: d[4] = 0, mark it used and enqueue it. It turns gray.

Pseudocode

 1 q.push(s); used[s]=1; d[s]=0; p[s]=-1 2 while (!q.empty()) { 3   v = q.front(); q.pop() 4   for (u in adj[v]) { 5     if (!used[u]) { 6       used[u] = 1 7       d[u] = d[v]+1; p[u] = v 8       q.push(u) 9 } } }  // d[] = shortest distances

1 / 1

Check

Three questions. Pick an answer to see why.

On the lecture’s graph from s = 4, what is the queue right after iteration 2 (vertex 5 has been processed)?

Why does plain BFS give wrong distances when edges have different weights?

Shortest route in a 1000 × 1000 grid maze, moving up, down, left or right. What does BFS cost?

Practice

Real problems to lock it in, easiest first.

CSESMessage Route beginner↗CSESLabyrinth intermediate↗LeetCodeRotting Oranges intermediate↗LeetCodeShortest Path in Binary Matrix intermediate↗CSESMonsters advanced↗