1. 从“单点”到“多点”为什么我们需要多源BFS在解决图论或网格类问题时广度优先搜索BFS是我们最熟悉的武器之一。它的经典应用场景是寻找从单一“起点”到单一“终点”的最短路径比如经典的迷宫问题。算法从起点出发像水波一样一层层向外扩散第一次到达终点时所经历的层数就是最短步数。这个模型直观、高效是算法入门必学。但现实中的问题往往更复杂。想象一下这样的场景在一片森林里同时有多个地方发生了火灾火势会以相同的速度向四周蔓延。我们关心的是整片森林被完全烧毁需要多少时间或者地图上有多个你的“基地”你需要派遣队伍去探索未知区域队伍从所有基地同时出发速度相同那么地图上每个位置被首次探索到的时间是多少再比如在一个社交网络中一个谣言从多个“源头用户”开始传播每个时间步传给其所有好友那么每个用户最早听到谣言的时间点是什么这些问题无法用传统的单源BFS来优雅地解决。如果你固执地分别从每个源头跑一次BFS然后对每个位置取所有BFS结果的最小值这在算法复杂度上是不可接受的相当于问题规模乘以源头数量。这时多源BFSMulti-source BFS就登场了。它的核心思想极其巧妙在初始化BFS队列时不是放入一个起点而是将所有源头同时放入队列并标记它们的初始距离通常为0。这样BFS的第一层就包含了所有源头接下来的扩散过程就是所有“波”同时、同速地向外推进。当一个位置第一次被任何一波“触及”时它所对应的步数就是它离其最近源头的最短距离。这个模型我们称之为“最小步数模型”。这里的“最小步数”不是指从A到B而是指地图上每个点到达离它最近的源点所需要的最少步数。多源BFS在一次遍历中就为整个地图的所有位置计算出了这个值效率是单源BFS无法比拟的。它解决了一类“多起点同速度求最近距离”问题的共性。2. 多源BFS的算法框架与核心实现细节理解了思想我们来看如何用代码实现。多源BFS在代码结构上与单源BFS几乎一致唯一的区别就在于队列的初始化。我们以一个经典的网格问题为例给定一个n x m的矩阵其中包含数字0和1。1代表“源点”比如火灾起火点、基地、谣言源头0代表普通区域。我们需要计算每个0位置距离其最近的1的曼哈顿距离即只能上下左右移动每次移动算一步。2.1 算法步骤拆解步骤一初始化这是与单源BFS唯一不同的地方。我们创建一个队列q和一个距离数组dist大小与地图相同初始化为一个特殊值如-1或INF表示未访问。 然后我们遍历整个地图将所有值为1的源点位置(i, j)将其坐标加入队列q。在dist[i][j]中将其距离设置为0源点到自己的距离为0。此时队列里已经包含了所有“第0层”的节点。步骤二标准BFS遍历接下来就是标准的BFS过程当队列不为空时取出队首节点(x, y)。遍历该节点的四个方向上、下、左、右的邻居(nx, ny)。检查邻居是否在地图范围内、是否未被访问过即dist[nx][ny] -1。如果满足条件则将邻居节点(nx, ny)加入队列。更新邻居的距离dist[nx][ny] dist[x][y] 1。这一步是关键它保证了每个点记录的是从最近源点出发的步数。步骤三输出结果BFS结束后dist数组中就存储了每个位置距离最近源点的最短步数。对于源点自身距离为0对于原本就是0的区域则得到了我们想要的结果。2.2 代码模板以C为例#include iostream #include queue #include cstring using namespace std; typedef pairint, int PII; const int N 1010; // 假设地图最大尺寸 int n, m; int g[N][N]; // 存储原始地图1为源点0为普通区域 int dist[N][N]; // 存储最短距离 queuePII q; // 方向数组上右下左 int dx[4] {-1, 0, 1, 0}; int dy[4] {0, 1, 0, -1}; void multiSourceBfs() { // 1. 初始化距离数组和队列 memset(dist, -1, sizeof dist); // -1表示未访问 for (int i 0; i n; i) { for (int j 0; j m; j) { if (g[i][j] 1) { // 找到源点 q.push({i, j}); dist[i][j] 0; // 源点距离为0 } } } // 2. 标准BFS过程 while (!q.empty()) { auto t q.front(); q.pop(); int x t.first, y t.second; for (int i 0; i 4; i) { int nx x dx[i]; int ny y dy[i]; // 检查边界、是否可访问这里判断是否为普通区域0且未访问 if (nx 0 nx n ny 0 ny m dist[nx][ny] -1) { dist[nx][ny] dist[x][y] 1; q.push({nx, ny}); } } } } int main() { // 假设已读入 n, m 和地图 g[][] multiSourceBfs(); // 输出结果 for (int i 0; i n; i) { for (int j 0; j m; j) { cout dist[i][j] ; } cout endl; } return 0; }注意在遍历邻居判断条件时dist[nx][ny] -1是最通用的“未访问”判断。有时题目可能对可移动区域有额外限制比如只能是陆地0不能是海洋-1则需要同时判断g[nx][ny]是否符合要求。核心是一个位置一旦被首次访问即距离值被更新其距离就是最小值之后不应再被更新。这是BFS“首次到达即最短”的性质保证的。3. 从模型到实战三大经典问题剖析掌握了模板我们来看几个力扣LeetCode上的经典题目它们都是多源BFS“最小步数模型”的直接或变形应用。通过这些问题你能更深刻地理解模型的威力。3.1 问题一地图分析LeetCode 1162题目简述你现在手里有一张N x N的网格地图每个格子要么是陆地1要么是海洋0。请找出一个海洋单元格这个海洋单元格到离它最近的陆地单元格的距离是最大的。并返回这个最大距离。如果地图上只有陆地或者只有海洋返回-1。问题转化这几乎就是多源BFS最小步数模型的“标准描述”。只不过源点是所有陆地格子1目标是所有海洋格子0。我们需要对每个海洋格子求出其到最近陆地的距离然后取其中的最大值。解题思路初始化队列和距离数组。遍历地图将所有陆地格子1作为源点入队距离设为0。执行多源BFS计算每个格子尤其是海洋格子到最近陆地的距离。BFS结束后遍历所有海洋格子0找出距离数组中的最大值。需要处理全陆地或全海洋的特殊情况。核心代码片段int maxDistance(vectorvectorint grid) { int n grid.size(); vectorvectorint dist(n, vectorint(n, -1)); queuepairint, int q; int lands 0; // 多源初始化 for (int i 0; i n; i) { for (int j 0; j n; j) { if (grid[i][j] 1) { q.push({i, j}); dist[i][j] 0; lands; } } } if (lands 0 || lands n * n) return -1; // 全海或全陆 // BFS int dirs[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; int maxDist 0; while (!q.empty()) { auto [x, y] q.front(); q.pop(); for (auto d : dirs) { int nx x d[0], ny y d[1]; if (nx0 nxn ny0 nyn dist[nx][ny]-1) { dist[nx][ny] dist[x][y] 1; maxDist max(maxDist, dist[nx][ny]); // 顺便更新最大值 q.push({nx, ny}); } } } return maxDist; }实操心得在BFS过程中可以一边扩散一边更新最大距离无需最后再遍历一次数组。这是一个常见的优化小技巧。另外处理全陆地或全海洋的边界情况是本题的一个易错点。3.2 问题二腐烂的橘子LeetCode 994题目简述在给定的m x n网格中每个单元格可以有以下三个值之一0代表空单元格1代表新鲜橘子2代表腐烂的橘子。每分钟任何与腐烂橘子相邻4个方向之一的新鲜橘子都会腐烂。返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能返回-1。问题转化这里的“源点”是所有初始就腐烂的橘子值为2。腐烂过程等同于从这些源点同时开始的BFS扩散。每分钟对应BFS的一层。我们需要计算所有新鲜橘子1被“感染”所需的时间也就是它被BFS访问到时所在的层数距离。最终答案是所有新鲜橘子被腐烂所需的最大时间层数。如果BFS结束后还有新鲜橘子未被访问到则返回-1。解题思路初始化队列将所有腐烂橘子位置入队并将其距离时间设为0。同时统计新鲜橘子的总数fresh。执行多源BFS。当从队列中取出一个腐烂橘子遍历其四个方向如果邻居是新鲜橘子1则将其腐烂可以原地修改网格为2或使用独立的dist数组距离为当前距离1并入队。每腐烂一个fresh计数减1。BFS结束后如果fresh为0返回过程中记录的最大时间否则返回-1。核心代码片段int orangesRotting(vectorvectorint grid) { int m grid.size(), n grid[0].size(); queuepairint, int q; int fresh 0, minutes 0; // 多源初始化腐烂橘子入队并统计新鲜橘子 for (int i 0; i m; i) { for (int j 0; j n; j) { if (grid[i][j] 2) q.push({i, j}); else if (grid[i][j] 1) fresh; } } if (fresh 0) return 0; // 没有新鲜橘子 // BFS int dirs[4][2] {{-1,0},{1,0},{0,-1},{0,1}}; while (!q.empty() fresh 0) { // fresh0 可提前结束 int sz q.size(); for (int i 0; i sz; i) { // 分层处理每分钟一层 auto [x, y] q.front(); q.pop(); for (auto d : dirs) { int nx x d[0], ny y d[1]; if (nx0 nxm ny0 nyn grid[nx][ny]1) { grid[nx][ny] 2; // 标记为腐烂 q.push({nx, ny}); fresh--; } } } minutes; // 一层结束时间1 } return fresh 0 ? minutes : -1; }避坑指南本题的关键在于分层BFS。因为我们要统计的是“分钟数”而BFS中每一层就代表了一分钟的扩散。代码中int sz q.size(); for (int i0; isz; i) {...}这个结构就是标准的分层遍历写法。在循环外minutes确保了时间计数的准确性。如果不分层直接使用dist数组记录步数最后取最大值也是可以的但分层写法在逻辑上更贴合题意。3.3 问题三01矩阵LeetCode 542题目简述给定一个由0和1组成的矩阵mat请输出一个大小相同的矩阵其中每个格子是mat中对应位置元素到最近的0的距离曼哈顿距离。问题转化这是最小步数模型的“镜像”问题。之前的题目是求每个位置到最近的1的距离这里是求每个位置到最近的0的距离。源点变成了所有的0。解题思路与“地图分析”问题几乎一模一样只是源点和目标互换。将所有0作为源点入队进行多源BFS计算所有1到最近0的距离。一个重要的思维扩展为什么这个问题不用对每个1做单源BFS找0假设矩阵大小为M x N其中有K个1。对每个1做BFS最坏时间复杂度是O(K * M * N)而使用多源BFS从所有0出发时间复杂度是O(M * N)。当K很大时比如矩阵中大部分是1前者效率极低。多源BFS巧妙地转换了视角将多个目标的搜索合并为一次从反方向源点出发的搜索这是其效率提升的本质。4. 进阶、变形与常见“坑点”多源BFS模型并不总是直接套用。在实际问题中它常常与其他概念结合或者设置了一些“陷阱”。4.1 结合状态压缩多源BFS 位运算有些问题中源点可能有不同的“类型”或“状态”。例如需要计算每个位置到最近的任意类型源点的距离但同时还需要知道它是被哪种类型源点最先到达的。或者问题要求找到一条路径需要收集所有类型的“钥匙”才能通过某些“锁”。这类问题通常需要将“位置”和“当前持有的状态”组合成一个新的节点(x, y, state)然后进行BFS。这里的state可以用一个整数的二进制位来表示这就是状态压缩。虽然这增加了BFS的维度但核心的“多源初始化”思想依然适用——你可能需要将所有初始状态如所有钥匙都未获取时的各个起点加入队列。经验之谈遇到网格上有门、钥匙、多种物品的问题要立刻联想到BFS 状态压缩。多源初始化时队列里放入的是(起点坐标, 初始状态)。判断新状态是否访问过需要一个三维的vis[x][y][state]数组。4.2 “超级源点”技巧有时题目中的源点并不是直接给出的网格点而是一些抽象的点或者源点之间本身有连接关系。我们可以引入一个虚拟的“超级源点”。将所有真实源点都与这个超级源点连接且距离为0。然后从超级源点做一次单源BFS其效果等同于从所有真实源点同时开始的多源BFS。这在处理一些图论问题时特别有用尤其是当源点列表是动态给出的时候。在代码实现上它避免了手动初始化多个源点入队的操作但在思维上不如直接的多源BFS直观。对于网格问题我们通常直接使用多源初始化队列的方法。4.3 易错点与调试技巧距离数组初始化一定要初始化为一个不可能出现的值如-1或INT_MAX用于判断是否访问过。如果初始化为0会导致无法区分未访问点和距离为0的源点。边界条件处理在遍历四个方向时务必先判断新坐标(nx, ny)是否在地图范围内再进行数组访问否则会导致运行时错误数组越界。访问标记的时机必须在将新节点加入队列的同时就标记为已访问或更新距离。如果等从队列取出时再标记可能会导致同一个节点被多次加入队列造成逻辑错误和性能下降。这是BFS的一个通用原则。结果的含义明确dist数组最终的含义。它存储的是“从最近的源点出发的步数”。对于源点本身距离是0。对于无法到达的点距离保持初始值如-1。输出结果前要清楚题目要求如何处理这些特殊情况。性能考量多源BFS的时间复杂度和空间复杂度与单源BFS遍历整个图相同都是O(VE)对于网格是O(M*N)。这是其高效的原因。如果遇到TLE超时检查是否是重复访问节点或者队列操作、条件判断写成了低效的形式。调试时可以打印出每一层BFS结束后的dist数组或队列状态观察扩散过程是否符合预期。对于复杂问题在纸上画一个小规模网格手动模拟算法流程是理解问题和排查bug最有效的方法。多源BFS加最小步数模型将看似复杂的多起点最短路径问题化简为一次高效的遍历。它的核心魅力在于这种“同时开始齐头并进”的思维转换。下次当你看到问题描述中出现“多个起点”、“同时扩散”、“最近距离”这些关键词时你应该能会心一笑知道该请出这位老朋友了。掌握它不仅能解决一大类算法题更能训练你化繁为简、转换问题视角的思维能力。