什么是多源 BFS？为什么可以同时从多个起点出发？
简化版
多源 BFS 就是把多个起点同时放入队列，距离都初始化为 0，然后像普通 BFS 一样一层层扩散。
它适合求「每个点到最近源点的距离」，比如地图上每个格子到最近水源、最近腐烂橘子、最近出口的距离。
本质上，多源 BFS 等价于新建一个超级源点，用 0 权边连接所有起点，再从超级源点做 BFS。
详细版
普通 BFS 从一个起点出发，适合无权图最短路。
多源 BFS 有多个起点：
for source in sources:
dist[source] = 0
queue.push(source)之后每次弹出队头，扩展邻居。如果邻居未访问，就设置距离并入队。
| 问题 | 多源 BFS 含义 |
|---|---|
| 腐烂橘子 | 所有腐烂橘子同时扩散 |
| 地图距离 | 所有目标点同时作为起点 |
| 最近出口 | 所有出口同时作为起点 |
它保证第一次访问到某点时，就是离任一源点的最短距离。
完整版教学
1. 普通 BFS 的最短路前提
在无权图中，BFS 按层扩展。
第 0 层是起点，第 1 层是一步可达节点，第 2 层是两步可达节点。
因此节点第一次被访问时，距离就是最短距离。
多源 BFS 只是把第 0 层从一个点变成多个点。
2. 多源 BFS 怎么初始化
关键是初始化队列。
queue = []
for s in sources:
dist[s] = 0
visited[s] = true
queue.push(s)所有源点同时进入队列，表示它们在时间 0 就已经存在。
多源 BFS 不是依次从每个源点跑 BFS，而是所有源点一起扩散。
3. 为什么第一次访问仍然最短
BFS 队列按层推进。
多个源点都在第 0 层，它们的邻居都在第 1 层，再往外是第 2 层。
某个节点第一次被访问时，说明从某个源点到它的距离已经是当前最小层数。其他源点如果以后再到达，只会是相同或更大的层数。
4. 超级源点怎么理解
可以想象额外增加一个虚拟节点 S。
它通过权重为 0 的边连接所有源点：
S -> s1
S -> s2
S -> s3从 S 出发做 BFS，就等价于把所有源点初始入队。
这个视角有助于理解为什么算法是正确的。
5. 和多次 BFS 的区别
如果有 K 个源点，每个源点都跑一次 BFS，复杂度可能是：
O(K * (V + E))多源 BFS 只跑一次：
O(V + E)| 做法 | 复杂度 | 是否推荐 |
|---|---|---|
| 每个源点单独 BFS | 高 | 源点少时勉强 |
| 多源 BFS | 低 | 推荐 |
6. 网格题怎么套
网格可以看成图。
每个格子是节点，上下左右是边。
例如腐烂橘子问题中：
- 把所有腐烂橘子入队；
- 每一层表示一分钟；
- 扩散到新鲜橘子时记录时间；
- 最后检查是否还有新鲜橘子。
这就是典型多源 BFS。
7. 适用边界是什么
多源 BFS 适合无权图，或者所有边权相同的图。
如果边权不同，就不能直接用 BFS，而要考虑多源 Dijkstra。
| 图类型 | 方法 |
|---|---|
| 无权图 | 多源 BFS |
| 等权图 | 多源 BFS |
| 非负加权图 | 多源 Dijkstra |
| 有负权边 | Bellman-Ford 类方法 |
8. 常见误区与追问
- 误区：多源 BFS 要对每个源点分别搜索。 正确做法是所有源点同时入队，只跑一次 BFS。
- 误区：队列里多个起点会破坏最短路。 它们都属于第
0层，BFS 层序性质仍然成立。 - 误区：多源 BFS 可以处理任意权重。 它只适合无权或等权图。
- 追问：怎么求每个点到最近 1 的距离？ 把所有值为 1 的点入队，然后多源 BFS。
- 追问：多源 Dijkstra 怎么做？ 把多个源点距离设为 0 后一起放入优先队列。