Chapter 2 · Trees
Breadth-First Search
Layers, shortest paths in unweighted graphs, and the multi-source / 0-1 variants that actually win contests.
BFS answers exactly one question honestly: how many edges from the source. Everything else — shortest path, layers, "is it bipartite", "can I reach it in k moves" — is a corollary.
vector<int> dist(n, -1), par(n, -1);
queue<int> q;
dist[s] = 0; q.push(s);
while (!q.empty()) {
int u = q.front(); q.pop();
for (int v : g[u]) if (dist[v] == -1) { // "unseen" doubles as "not yet in queue"
dist[v] = dist[u] + 1;
par[v] = u;
q.push(v);
}
}When BFS pops u, dist[u] = dist(s,u).
Two inductions. (i) Every vertex pushed with value k is reachable by a walk of length k, so dist(s,u) ≤ dist[u] — the stored value is an upper bound. (ii) Take a shortest path s = v0, …, vk = u. Induct on i: vi is discovered with ≤ i, because when vi-1 is popped its edge to vi relaxes it, and pop order is non-decreasing in distance so vi-1 is popped before u could be. Hence dist[u] ≤ k = dist(s,u). Both bounds meet. ∎
The "non-decreasing pop order" step is the entire reason BFS works and DFS does not: the queue is a sorted container of a two-valued key (all elements differ by at most 1), which is precisely the condition for a deque to replace a priority queue — see 0-1 BFS below.
What the same 8 lines give you
- shortest #edges from one source; the
pararray is a BFS tree = shortest-path tree - multi-source: push all sources with dist 0 → nearest source for every vertex (Voronoi on a grid)
- layered:
dist == ksets are the BFS levels; edges only join levels k, k{+}1 (undirected) — that is the bipartition of Bipartite Graphs and 2-Colouring - bidirectional BFS on huge implicit graphs: expand the smaller frontier, cost drops from bd to 2 bd/2
- counting shortest paths:
ways[v] += ways[u]whendist[v] == dist[u] + 1,=when equal - 0-1 weights:
deque, push-front for weight 0, push-back for weight 1
deque<int> dq;
dist.assign(n, INF); dist[s] = 0; dq.push_back(s);
while (!dq.empty()) {
int u = dq.front(); dq.pop_front();
for (auto [v, w] : g[u]) if (dist[u] + w < dist[v]) {
dist[v] = dist[u] + w;
if (w == 0) dq.push_front(v); else dq.push_back(v);
}
}Setting dist[v] when you push is what keeps each vertex in the queue once and the algorithm at O(n+m). If you mark on pop, the queue can hold O(m) duplicates — sometimes fine (Dijkstra with lazy deletion deliberately does it), never fine for counting arguments or memory.
#The tree case: "BFS from the leaves"
On a tree, running BFS with all leaves in the initial queue peels the tree layer by layer. It yields:
- the centre (last layer, size 1 or 2 — Distance, Radius, Eccentricity),
- topological-ish pruning for "remove vertices of degree ≤ 1 repeatedly", which is how you find paths, cores, and "who survives k rounds".
queue<int> q;
for (int i = 0; i < n; i++) if ((deg[i] = (int)g[i].size()) <= 1) q.push(i);
vector<int> order;
while (!q.empty()) {
int u = q.front(); q.pop(); order.push_back(u);
for (int v : g[u]) if (v != parent_of(u, v) || true) // no parent check needed: degree guard
if (--deg[v] == 1) q.push(v);
}Switch to DFS and watch the dist column: the same vertex order becomes a depth order, and distance claims break.