好推建站北京架设网站
多源 BFS 是一种解决 边权为 1 的多源最短路问题 的高效算法。其核心思想是将所有源点视为一个“超级源点”，通过一次 BFS 遍历即可计算所有节点到最近源点的最短距离。以下从原理、实现和代码示例三个方面深入讲解：
目录
一、原理分析
1. 单源 BFS vs 多源 BFS
2. 正确性证明
3. 时间复杂度
二、C++ 实现步骤
1. 初始化
2. BFS 扩展
三、代码示例
四、代码解释
初始化阶段
BFS 扩展阶段
五、应用场景
六、注意事项
一、原理分析
1. 单源 BFS vs 多源 BFS
-
单源 BFS：从单一源点出发，逐层扩展，记录每个节点到该源点的最短距离。
-
多源 BFS：将多个源点 同时加入队列，作为 BFS 的初始层。每个节点被首次访问时，记录的是到最近源点的最短距离。
2. 正确性证明
-
BFS 的逐层扩展特性保证：当某个节点被首次访问时，其路径长度即为最短距离。
-
所有源点同时作为初始层，相当于它们处于“第 0 层”，后续扩展的层数即为到最近源点的距离。
3. 时间复杂度
-
与单源 BFS 相同，时间复杂度为 O(N)（假设共 N 个节点），每个节点和边仅被处理一次。
二、C++ 实现步骤
以二维网格为例，假设 grid 表示网格，其中 1 为源点，0 为可通行节点。目标是计算每个节点到最近源点的距离。
1. 初始化
-
队列：将所有源点坐标加入队列。
-
距离数组：源点距离初始化为
0，其他节点初始化为-1（表示未访问）。
2. BFS 扩展
-
从队列中取出节点，检查其四个方向（上、下、左、右）。
-
若相邻节点未被访问过，更新其距离并加入队列。
三、代码示例
#include <vector>
#include <queue>
using namespace std;vector<vector<int>> multiSourceBFS(vector<vector<int>>& grid) {int rows = grid.size();int cols = grid[0].size();queue<pair<int, int>> q;vector<vector<int>> dist(rows, vector<int>(cols, -1));// 初始化：将所有源点加入队列，并设置距离为 0for (int i = 0; i < rows; i++) {for (int j = 0; j < cols; j++) {if (grid[i][j] == 1) {q.push({i, j});dist[i][j] = 0;}}}// 四个移动方向：上、下、左、右vector<pair<int, int>> dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};while (!q.empty()) {auto [x, y] = q.front();q.pop();for (auto [dx, dy] : dirs) {int nx = x + dx;int ny = y + dy;// 检查边界和是否已访问if (nx >= 0 && nx < rows && ny >= 0 && ny < cols && dist[nx][ny] == -1) {dist[nx][ny] = dist[x][y] + 1;q.push({nx, ny});}}}return dist;
}四、代码解释
-
初始化阶段
-
遍历网格，将所有源点（值为
1）的坐标加入队列，并设置其距离为0。 -
其他节点的距离初始化为
-1，表示未访问。
-
-
BFS 扩展阶段
-
从队列中取出节点，检查四个方向的相邻节点。
-
若相邻节点在网格内且未被访问，更新其距离为当前节点距离
+1，并将其加入队列。
-
五、应用场景
-
计算多个起点到所有节点的最短距离（如疫情传播模拟、火源蔓延模型）。
-
地图中多个商店到用户的最短路径计算。
六、注意事项
-
边权必须为 1：若边权不同，需使用 Dijkstra 或 Floyd-Warshall 算法。
-
空间优化：可直接在原数组上修改距离，避免额外空间开销。
-
性能优势：相比暴力法（每个源点单独 BFS），时间复杂度从 O(kN) 优化到 O(N)，其中 k 是源点数量。
通过多源 BFS，我们能够以高效的方式解决多个起点同时扩散的最短路径问题，是图论中一种重要的优化技巧。