---
title: Breadth-First Search
summary: Layers, shortest paths in unweighted graphs, and the multi-source / 0-1 variants that actually win contests.
difficulty: core
tags: [traversal, shortest-path]
time: n + m
space: n
prereq: [foundations/representation]
see: [trees/dfs, shortest/sparse-tricks]
---

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.

```cpp bfs.cpp
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);
    }
}
```

:::theorem title="Correctness"
When BFS pops $u$, $\operatorname{dist}[u] = \operatorname{dist}(s,u)$.
:::

:::proof
Two inductions. (i) Every vertex pushed with value $k$ is reachable by a walk of length $k$, so $\operatorname{dist}(s,u) \le \operatorname{dist}[u]$ — the stored value is an *upper* bound. (ii) Take a shortest path $s = v_0, \dots, v_k = u$. Induct on $i$: $v_i$ is discovered with $\le i$, because when $v_{i-1}$ is popped its edge to $v_i$ relaxes it, and pop order is non-decreasing in distance so $v_{i-1}$ is popped before $u$ could be. Hence $\operatorname{dist}[u] \le k = \operatorname{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.

:::props title="What the same 8 lines give you"
- shortest #edges from one source; the `par` array 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 == k` sets are the BFS levels; edges only join levels $k, k{+}1$ (undirected) — that is the bipartition of @foundations/bipartite
- **bidirectional BFS** on huge implicit graphs: expand the smaller frontier, cost drops from $b^d$ to $2 b^{d/2}$
- **counting shortest paths**: `ways[v] += ways[u]` when `dist[v] == dist[u] + 1`, `=` when equal
- **0-1 weights**: `deque`, push-front for weight 0, push-back for weight 1
:::

```cpp zero-one-bfs.cpp
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);
    }
}
```

:::warning title="Mark at push time, not pop time"
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 — @trees/distance),
- **topological-ish pruning** for "remove vertices of degree ≤ 1 repeatedly", which is how you find paths, cores, and "who survives $k$ rounds".

```cpp peel.cpp
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);
}
```

:::demo id="traversal" caption="Switch to DFS and watch the `dist` column: the same vertex order becomes a depth order, and distance claims break."
:::

:::problems
- [[CSES 1193]] Labyrinth | https://cses.fi/problemset/task/1193 | easy | grid BFS
- [[CSES 1194]] Monsters | https://cses.fi/problemset/task/1194 | core | multi-source BFS
- [[CF 1242B]] 0-1 MST | https://codeforces.com/problemset/problem/1242/B | core | dense graph, so traverse the complement
- [[CSES 1670]] Swap Game | https://cses.fi/problemset/task/1670 | core | implicit graph BFS
:::