多源BFS：解决LeetCode多源最短路径问题

多源BFS（多源最短路径）知识点整理

一、核心概念

1. 单源最短路径 vs 多源最短路径

二、多源BFS的核心思想

1. 适用场景

边权为1的网格/图结构（如0-1矩阵、迷宫）

需要计算每个节点到最近源点的距离（如到最近陆地/水域的距离）

2. 核心解法（两种思路）

解法一：暴力单源BFS（不推荐）

思路：对每个源点单独执行一次单源BFS，取每个节点到所有源点的距离最小值。

缺点：时间复杂度为 O(k*(V+E))（k为源点数量），当源点数量多时极易超时。

解法二：超级源点法（多源BFS，推荐）

核心思想：把所有源点当成一个“超级起点”，一次性加入队列，再执行BFS扩散。

原理：所有源点初始距离均为0，BFS按层向外扩散，天然保证每个节点第一次被访问时，距离就是到最近源点的距离。

优势：时间复杂度为 O(V+E)，仅需一次BFS遍历，效率极高。

三、多源BFS的正确性（感性理解）

1. 队列初始状态：所有源点同时入队，距离均为0，相当于“同一层”的起点。

2. BFS扩散逻辑：按层向外扩展，每一层的节点距离比上一层+1，天然保证“第一次访问=最近距离”。

3. 直观类比：多个“水波”同时向外扩散，最先到达的位置，就是离最近源点的距离。

四、多源BFS代码模板（通用）

// 方向数组（上下左右） int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; class Solution { public: vector<vector<int>> multiSourceBFS(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); // dist矩阵：存储每个节点到最近源点的距离，初始为-1（未访问） vector<vector<int>> dist(m, vector<int>(n, -1)); queue<pair<int, int>> q; // 1. 初始化：把所有源点加入队列，标记距离为0 for (int i = 0; i < m; i++) { for (int j = 0; j < n; j++) { if (grid[i][j] == 源点条件) { dist[i][j] = 0; q.push({i, j}); } } } // 2. 多源BFS扩散 while (!q.empty()) { auto [a, b] = q.front(); q.pop(); // 遍历四个方向 for (int i = 0; i < 4; i++) { int x = a + dx[i]; int y = b + dy[i]; // 检查：坐标合法 + 未被访问 if (x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) { dist[x][y] = dist[a][b] + 1; q.push({x, y}); } } } return dist; } };

题目1：矩阵（LeetCode 542. 01）

1. 题目描述

提示：

• m == mat.length
• n == mat[i].length
• 1 <= m, n <= 104
• 1 <= m * n <= 104
• mat[i][j] is either 0 or 1.
• mat中至少有一个0

2. 核心知识点：多源BFS

1） 算法思路对比

对于“求矩阵中每个元素到最近0的距离”，有两种常见思路：

2） 多源BFS的核心原理

多源BFS的关键在于：

把所有的 0 视为“多个起点”，一次性全部加入队列

以“层序遍历”的方式向外扩展，每扩展一层，距离就+1

第一次访问到某个节点时，得到的距离就是它到最近0的最短距离（因为所有0同时扩散，谁先到达就是最近的）

class Solution { // 上下左右四个方向的偏移量 int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; public: vector<vector<int>> updateMatrix(vector<vector<int>>& mat) { int m = mat.size(), n = mat[0].size(); // dist[i][j] = -1 表示该节点未被访问 // dist[i][j] >= 0 表示该节点到最近0的距离 vector<vector<int>> dist(m, vector<int>(n, -1)); queue<pair<int, int>> q; // BFS队列，存储坐标(i,j) // 步骤1：把所有的0作为源点，加入队列，并标记距离为0 for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(mat[i][j] == 0) { q.push({i, j}); dist[i][j] = 0; } } } // 步骤2：层序BFS扩展，计算每个节点的最短距离 while(q.size()) { auto [a, b] = q.front(); // 取出队首节点（当前层的节点） q.pop(); // 遍历四个方向 for(int i = 0; i < 4; i++) { int x = a + dx[i]; int y = b + dy[i]; // 检查边界条件 + 节点是否未被访问（dist[x][y] == -1） if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) { // 当前节点的距离 = 父节点距离 + 1 dist[x][y] = dist[a][b] + 1; q.push({x, y}); // 加入队列，继续向外扩展 } } } return dist; } };

3. 关键细节拆解

1） 方向数组
dx[4] 和 dy[4] 是上下左右四个方向的偏移量，简化了方向遍历的代码，避免写4个重复的判断语句。

2） 距离数组初始化
dist 数组初始化为 -1，有两个作用：标记节点是否被访问过；存储最终的最短距离，0的距离初始化为0，后续扩展时自动+1

3） 多源队列初始化
把所有0一次性加入队列，相当于多个起点同时开始BFS，保证了“第一次访问到的节点就是最短距离”的正确性。

4） 边界与访问判断
x >= 0 && x < m && y >= 0 && y < n 确保坐标不越界；dist[x][y] == -1 确保节点只被访问一次，避免重复计算。

5）vector<vector<int>> dist(m, vector<int>(n, -1));创建一个二维int数组，行数是 m，每行有 n 个元素，所有元素初始值都设为 -1。

vector<vector<int>>定义二维vector，里面存的是int整数。

(m, vector<int>(n, -1))

第一个参数 m：外层vector有 m行

vector<int>(n, -1)：构造一个长度为n、每个元素都是-1的一维vector

整句就是：生成 m行n列，全部初始值 -1

4. 复杂度分析

时间复杂度：O(m×n)，矩阵中的每个节点最多被访问一次，队列操作也是O(1)级别的，整体线性时间复杂度。

空间复杂度：O(m×n)，距离数组 dist 占用O(m×n)空间；队列最多存储所有节点，最坏情况也是O(m×n)。

题目2：飞地的数量（LeetCode 1020）

1. 题目描述

2. 核心解法思路（正难则反）

核心思想：不直接找“被包围的陆地”，而是反向标记“能到达边界的陆地”，剩下的 1 就是飞地。

步骤拆解：

1） 标记边界及可达陆地：从矩阵边界上的 1 出发，通过多源BFS/DFS，把所有与边界连通的 1 标记为“可达边界”。

2） 统计飞地数量：遍历整个矩阵，统计未被标记的 1 的数量，即为飞地总数。

class Solution { // 上下左右四个方向的偏移量（x轴：行，y轴：列） int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; public: int numEnclaves(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); // vis：标记是否为“能到达边界的陆地”，初始为false vector<vector<bool>> vis(m, vector<bool>(n)); // 队列：BFS的队列，存储坐标（i,j） queue<pair<int, int>> q; // 1. 把边界上的1加入队列，作为多源BFS的起点 for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { // 判断是否为边界：第一行/最后一行/第一列/最后一列 if(i == 0 || i == m - 1 || j == 0 || j == n - 1) { // 如果边界上是陆地，加入队列并标记为可达 if(grid[i][j] == 1) { q.push({i, j}); vis[i][j] = true; } } } } // 2. 多源BFS：从所有边界1出发，标记所有连通的可达陆地 while(!q.empty()) { // 取出队首坐标 auto [a, b] = q.front(); q.pop(); // 遍历四个方向 for(int i = 0; i < 4; i++) { // 计算相邻坐标 int x = a + dx[i], y = b + dy[i]; // 检查：坐标合法 + 是陆地 + 未被标记 if(x >= 0 && x < m && y >= 0 && y < n && grid[x][y] == 1 && !vis[x][y]) { vis[x][y] = true; q.push({x, y}); } } } // 3. 统计结果：未被标记的1，就是无法到达边界的飞地 int ret = 0; for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(grid[i][j] == 1 && !vis[i][j]) { ret++; } } } return ret; } };

3. 关键知识点拆解

1） 多源BFS（核心算法）

概念：BFS的起点不止一个，同时从多个起点开始向外扩散遍历。

本题作用：一次性处理所有边界上的 1，高效标记所有能到达边界的连通陆地。

优势：相比单源BFS逐个遍历边界，多源BFS的时间复杂度更优，整体为 O(mn)。

2） 方向数组（dx/dy）

定义：int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0};

含义：对应“右、左、下、上”四个方向的坐标偏移，简化相邻单元格的遍历逻辑，避免写4次重复的判断代码。

3）vector<vector<bool>> vis标记数组

作用：记录哪些陆地是“能到达边界”的，避免重复遍历，也避免修改原矩阵（保护输入数据）。

初始值：false，表示“未被标记”；遍历后设为true，表示“可达边界”。

4） 边界条件判断

边界坐标判断：i == 0 || i == m - 1 || j == 0 || j == n - 1

相邻坐标合法性判断：x >= 0 && x < m && y >= 0 && y < n，防止数组越界访问。

4. 算法复杂度分析

时间复杂度：O(m * n)，矩阵中每个单元格最多被访问一次（BFS遍历+最后统计各一次），因此整体为线性复杂度。

空间复杂度：O(m * n)，标记数组vis的大小为m*n，队列在最坏情况下（全为陆地）也需要存储m*n个元素。

题目3：地图中的最高点（LeetCode 1765）

1. 题目描述

提示：

• m == isWater.length
• n == isWater[i].length
• 1 <= m, n <= 1000
• isWater[i][j]要么是0，要么是1。
• 至少有1个水域格子。

注意：本题与 542 题相同。

2. 核心解法思路

核心思想

这是一道典型的多源BFS问题，核心逻辑是：

1） 所有水域格子的高度为0，作为BFS的起点；

2） 从水域格子出发向外扩散，每个陆地格子的高度等于其到最近水域格子的距离；

3） 这样分配高度，天然满足“相邻格子高度差≤1”的规则，同时能让最高高度值最大。

步骤拆解

1) 初始化：创建距离矩阵dist（即最终的高度矩阵），初始值为-1（表示未访问）；

2) 多源起点入队：将所有水域格子（isWater[i][j]==1）加入队列，标记高度为0；

3) 多源BFS扩散：从所有水域格子同时向外遍历，每个相邻未访问格子的高度设为当前格子高度+1；

4) 返回结果：遍历完成后，dist矩阵即为符合要求的高度矩阵。

class Solution { // 上下左右四个方向的偏移量 int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; public: vector<vector<int>> highestPeak(vector<vector<int>>& isWater) { int m = isWater.size(), n = isWater[0].size(); // dist矩阵：存储每个格子的高度，初始为-1表示未访问 vector<vector<int>> dist(m, vector<int>(n, -1)); // 队列：BFS存储坐标（i,j） queue<pair<int, int>> q; // 1. 把所有水域格子作为多源起点加入队列 for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(isWater[i][j]) { dist[i][j] = 0; // 水域格子高度为0 q.push({i, j}); } } } // 2. 多源BFS：从所有水域格子向外扩散 while(!q.empty()) { auto [a, b] = q.front(); q.pop(); // 遍历四个方向 for(int i = 0; i < 4; i++) { int x = a + dx[i], y = b + dy[i]; // 检查：坐标合法 + 未被访问（dist[x][y]==-1） if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) { // 相邻格子高度 = 当前格子高度 + 1 dist[x][y] = dist[a][b] + 1; q.push({x, y}); } } } return dist; } };

3. 关键知识点拆解

1) 多源BFS（核心算法）

概念：同时从多个起点（本题中所有水域格子）开始向外扩散遍历的BFS算法。

本题作用：一次性计算每个陆地格子到最近水域格子的距离，天然满足“相邻高度差≤1”的规则。

优势：相比单源BFS逐个处理水域格子，多源BFS的时间复杂度为O(mn)，效率更高。

2) 方向数组（dx/dy）

定义：int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0};

含义：对应“右、左、下、上”四个方向的坐标偏移，简化相邻单元格的遍历逻辑。

3) vector<vector<int>> dist 矩阵

作用：同时作为访问标记数组和高度结果矩阵，避免额外空间开销。

初始值：-1表示“未访问”；水域格子初始设为0；陆地格子在BFS中被赋值为到最近水域的距离。

4. 算法复杂度分析

时间复杂度：O(m * n)，矩阵中每个单元格最多被访问一次，BFS遍历的总时间为线性复杂度。

空间复杂度：O(m * n)，距离矩阵dist的大小为m*n，队列在最坏情况下（全为水域格子）也需要存储m*n个元素。

题目4：地图分析（LeetCode 1162）

1. 题目描述

提示：

• n == grid.length
• n == grid[i].length
• 1 <= n <= 100
• grid[i][j]不是0就是1

2. 核心解法思路

核心思想

这是一道典型的多源BFS问题，和你之前学的「地图中的最高点」思路几乎完全一致：

1） 所有陆地格子作为BFS的起点，距离初始为0；

2） 从陆地格子向外扩散，每个海洋格子的距离等于它到最近陆地格子的曼哈顿距离；

3） 遍历过程中记录最大的距离值，即为题目所求的答案。

步骤拆解

1） 初始化：创建距离矩阵 dist，初始值为 -1（表示未访问）；

2） 多源起点入队：将所有陆地格子（grid[i][j]==1）加入队列，标记距离为 0；

3） 多源BFS扩散：从所有陆地格子同时向外遍历，每个相邻未访问格子的距离设为当前格子距离+1；

4） 记录最大值：遍历过程中不断更新最大距离值，最后返回该值（若所有格子都是陆地，返回 -1）。

class Solution { // 上下左右四个方向的偏移量 int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0}; public: int maxDistance(vector<vector<int>>& grid) { int m = grid.size(), n = grid[0].size(); // dist矩阵：存储每个格子到最近陆地的距离，初始为-1表示未访问 vector<vector<int>> dist(m, vector<int>(n, -1)); queue<pair<int, int>> q; // 1. 把所有陆地格子作为多源起点加入队列 for(int i = 0; i < m; i++) { for(int j = 0; j < n; j++) { if(grid[i][j] == 1) { dist[i][j] = 0; q.push({i, j}); } } } // 2. 多源BFS：从陆地格子向外扩散，计算每个海洋格子到最近陆地的距离 int ret = -1; // 初始为-1（无海洋的情况） while(!q.empty()) { auto [a, b] = q.front(); q.pop(); for(int i = 0; i < 4; i++) { int x = a + dx[i], y = b + dy[i]; // 检查：坐标合法 + 未被访问（dist[x][y]==-1） if(x >= 0 && x < m && y >= 0 && y < n && dist[x][y] == -1) { dist[x][y] = dist[a][b] + 1; q.push({x, y}); // 更新最大距离值 ret = max(ret, dist[x][y]); } } } return ret; } };

3. 关键知识点拆解

1） 多源BFS（核心算法）

概念：同时从多个起点（本题中所有陆地格子）开始向外扩散遍历的BFS算法。

本题作用：一次性计算每个海洋格子到最近陆地格子的距离，天然保证每个格子的距离是最近的。

优势：相比单源BFS逐个处理陆地格子，多源BFS的时间复杂度为 O(n²)，效率更高，且不会重复计算。

2） 方向数组（dx/dy）

定义：int dx[4] = {0, 0, 1, -1}; int dy[4] = {1, -1, 0, 0};

含义：对应“右、左、下、上”四个方向的坐标偏移，简化相邻单元格的遍历逻辑，避免重复写判断代码。

3） 距离矩阵 dist

作用：同时作为访问标记数组和距离结果矩阵，避免额外空间开销。

初始值：-1 表示“未访问”；陆地格子初始设为 0；海洋格子在BFS中被赋值为到最近陆地的距离。

4. 算法复杂度分析

时间复杂度：O(n²)，矩阵中每个单元格最多被访问一次，BFS遍历的总时间为线性复杂度。

空间复杂度：O(n²)，距离矩阵 dist 的大小为 n×n，队列在最坏情况下（全为陆地格子）也需要存储 n×n 个元素。