本讲定位：图论系列第三讲，把第 02 讲那个只会处理”边权全为 1 的普通图”的 BFS 推向四个方向：多源 BFS（$k$ 个起点一起入队，$O(k(n+m))$ 变 $O(n+m)$）、01-BFS（边权只有 0 和 1 时用双端队列，实测比堆优化 Dijkstra 快 5.8 倍）、双向 BFS（两头对撞，八数码上实测省掉 95%～98% 的出队）、状态图 BFS（把”局面”当结点——本系列最重要的一次思维转换）。四项都做了实测：多源三种写法对拍 5000 组一致；01-BFS 与 Dijkstra 对拍 7200 组一致，而”照搬第 02 讲的入队即定值写法”错 46%～68%；八数码三种实现对拍 400 组一致，康托展开比
map判重快 6 倍，双向 BFS 在最远局面上比单向快 13 倍——但无解时双向反而更慢（实测出队 263191 vs 181440），这个反例值得单独记住。文中所有代码经g++ -O2 -std=c++14 -Wall编译运行，P1332、P1379、P4667 三道例题均与洛谷官方样例核对。前置知识：第 02 讲的 BFS 模板与”层数即无权最短路”这条结论及其证明（必须先学，本讲全部内容都是在讨论这个证明的前提何时成立、如何绕开）；
deque的push_front/push_back/pop_front；map的基本用法。适合对象：第 2 节（多源）与第 5 节（状态图）标 J⭐，是 CSP-J 复赛的进阶考点，八数码类题目 J 组时有出现；第 3 节（01-BFS）标 S，第 4 节（双向 BFS）标 S⭐⭐，第一轮可跳过。建议顺序：先学第 2、5 节，第 3 节在学完第 05 讲 Dijkstra 后回头看会更清楚。
第 02 讲证明了：无权图上 BFS 的层数就是最短路。证明的核心是一句话——
当
dis[u] = k的点 $u$ 出队时，所有真实距离 $\le k$ 的点都已经被标记过了。
这句话成立的唯一前提是”每条边长度恰好为 1”。本讲的四种进阶，本质上都是在处理这个前提：
| 形态 | 前提被破坏了吗 | 怎么办 |
|---|---|---|
| 多源 BFS | 没破坏，只是起点变多了 | 所有源点一起入队即可（第 2 节） |
| 01-BFS | 破坏了：有长度为 0 的边 | 队列换双端队列，0 边压队首（第 3 节） |
| 双向 BFS | 没破坏，只是想少搜一点 | 从起点和终点同时搜（第 4 节） |
| 状态图 BFS | 没破坏，但”点”要自己造出来 | 状态编号 + 判重（第 5 节） |
其中第 5 节是本讲真正的重点——前三节是技巧，第 5 节是世界观。
P1332 血色先锋队：$n \times m$ 的网格，$a$ 个位置一开始就被感染。每一单位时间，感染会向四个方向各扩散一格。给 $b$ 个指定位置，问它们各自在什么时刻被感染。
朴素做法：对每个感染源跑一次 BFS，逐点取 $\min$。复杂度 $O(a \cdot nm)$。$a$ 可以和 $nm$ 同阶，那就是 $O((nm)^2)$，挂。
queue<pair<int,int> > q;
for (每个源点 (x,y)) {
if (dis[x][y] == -1) { dis[x][y] = 0; q.push(make_pair(x, y)); } // 全部 dis = 0
}
// 剩下的循环体和单源 BFS 一字不改
就这样，没有别的了。 代码和单源 BFS 唯一的差别是”初始入队的点从 1 个变成 $a$ 个，dis 全设 0”。
为什么对？两种解释，任选一种：
dis 都是 0，正是”$S$ 到它们距离 0”的直接体现。dis = 0 的点，队列仍然满足”从队首到队尾 dis 非降且极差 $\le 1$“这个不变量。整个归纳法一字不用改。