BFS解决----多源最短路径问题

一、多源最短路径问题定义

        给定一个图，其中包含多个起点和一个终点，多源最短路径问题要求找到从任一起点到终点的最短路径长度。

二、BFS算法解决多源最短路径的步骤

1. 初始化：

   • 创建一个队列来存储待处理的节点。

   • 创建一个距离数组来存储从起点到每个节点的最短距离，初始时，除了起点外，其他节点的距离设置为无穷大（或一个很大的数）。

   • 创建一个前驱数组来存储每个节点的前一个节点，以便重建路径。

2. BFS过程：

   • 将所有起点加入队列，并将它们的距离设置为0。

   • 当队列不为空时，重复以下步骤：

     • 从队列中取出一个节点，检查其所有邻接节点。

     • 对于每个邻接节点，如果通过当前节点到达它的距离更短，则更新它的距离，并将其加入队列。

     • 同时，记录到达该邻接节点的路径（即前驱节点）。

3. 重建路径：

   • 从终点开始，使用前驱数组回溯找到路径。

4. 返回结果：

   • 返回从所有起点到终点的最短路径长度。

三、相关例题

1.01矩阵

542. 01 矩阵 - 力扣（LeetCode）

1.题目解析

给定一个由 0 和 1 组成的矩阵 mat ，请输出一个大小相同的矩阵，其中每一个格子是 mat 中对应位置元素到最近的 0 的距离。

两个相邻元素间的距离为 1 。

2.示例

示例 1：

输入：mat = [[0,0,0],[0,1,0],[0,0,0]]
输出：[[0,0,0],[0,1,0],[0,0,0]]

示例 2：

输入：mat = [[0,0,0],[0,1,0],[1,1,1]]
输出：[[0,0,0],[0,1,0],[1,2,1]]

3.解题思路

        从 0 开始层序遍历，并且记录遍历的层数。当第⼀次碰到 1 的时候，当前的层数 就是这个 1 离 0 的最短距离。

1. 初始化距离矩阵和队列

   • 创建一个与输入矩阵mat大小相同的距离矩阵dis，并将其所有值初始化为-1，表示尚未搜索过。

   • 创建一个队列q，用于存储当前搜索的节点。

2. 将所有0值单元格加入队列

   • 遍历输入矩阵mat，将所有值为0的单元格坐标加入队列，并将其在距离矩阵dis中的值设为0。

3. 广度优先搜索（BFS）

   • 从队列中取出一个节点（坐标），检查其上下左右四个方向的相邻节点。

   • 如果相邻节点在矩阵范围内且尚未被访问过（即dis[x][y] == -1），则将其在距离矩阵中的值设为当前节点的距离加1，并将该节点加入队列。

   • 重复上述过程，直到队列为空。

4. 返回结果

   • 最终，距离矩阵dis中的每个值即为该位置到最近的0值单元格的距离。

4.代码实现

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] != -1 表⽰：最短距离vector<vector<int>> dis(m, vector<int>(n, -1));queue<pair<int, int>> q;//把所有原点都加入到队列里for(int i = 0; i < m; i++)for(int j = 0; j < n; j++)if(mat[i][j] == 0){q.push({i, j});dis[i][j] = 0;}//一层一层的往外扩while(q.size()){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 && dis[x][y] == -1){dis[x][y] = dis[a][b] + 1;q.push({x, y});}}}return dis;}
};

2.飞地的数量

1020. 飞地的数量 - 力扣（LeetCode）

1.题目解析

给你一个大小为 m x n 的二进制矩阵 grid ，其中 0 表示一个海洋单元格、1 表示一个陆地单元格。

一次 移动 是指从一个陆地单元格走到另一个相邻（上、下、左、右）的陆地单元格或跨过 grid 的边界。

返回网格中 无法 在任意次数的移动中离开网格边界的陆地单元格的数量。

2.示例

示例 1：

输入：grid = [[0,0,0,0],[1,0,1,0],[0,1,1,0],[0,0,0,0]]
输出：3
解释：有三个 1 被 0 包围。一个 1 没有被包围，因为它在边界上。

示例 2：

输入：grid = [[0,1,1,0],[0,0,1,0],[0,0,1,0],[0,0,0,0]]
输出：0
解释：所有 1 都在边界上或可以到达边界。

3.解题思路

        从边界上的1开始进行一次搜索，找到与外相连的地，并标记。然后对里面没有搜索过的1，进行搜索。

4.代码实现

class Solution {int dx[4] = {0, 0, 1, -1};int dy[4] = {1, -1, 0, 0};int m, n; 
public:int numEnclaves(vector<vector<int>>& grid) {m = grid.size(), n = grid[0].size();//创建一个bool数组，判断有没有搜索过vector<vector<bool>> vis(m, vector<bool>(n));queue<pair<int, int>> q;//遍历周围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;}}}while(q.size()){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]){q.push({x, y});vis[x][y] = true;}}}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.地图中的最高点

1765. 地图中的最高点 - 力扣（LeetCode）

1.题目解析

给你一个大小为 m x n 的整数矩阵 isWater ，它代表了一个由 陆地 和 水域 单元格组成的地图。

• 如果 isWater[i][j] == 0 ，格子 (i, j) 是一个 陆地 格子。
• 如果 isWater[i][j] == 1 ，格子 (i, j) 是一个 水域 格子。

你需要按照如下规则给每个单元格安排高度：

• 每个格子的高度都必须是非负的。
• 如果一个格子是 水域 ，那么它的高度必须为 0 。
• 任意相邻的格子高度差 至多 为 1 。当两个格子在正东、南、西、北方向上相互紧挨着，就称它们为相邻的格子。（也就是说它们有一条公共边）

找到一种安排高度的方案，使得矩阵中的最高高度值 最大 。

请你返回一个大小为 m x n 的整数矩阵 height ，其中 height[i][j] 是格子 (i, j) 的高度。如果有多种解法，请返回 任意一个 。

2.示例

示例 1：

输入：isWater = [[0,1],[0,0]]
输出：[[1,0],[2,1]]
解释：上图展示了给各个格子安排的高度。
蓝色格子是水域格，绿色格子是陆地格。

示例 2：

输入：isWater = [[0,0,1],[1,0,0],[0,0,0]]
输出：[[1,1,0],[0,1,1],[1,2,2]]
解释：所有安排方案中，最高可行高度为 2 。
任意安排方案中，只要最高高度为 2 且符合上述规则的，都为可行方案

3.解题思路

和上一道题相似

关键逻辑解释

• height[x][y] == -1的作用

  • 在BFS扩展过程中，只有当height[x][y] == -1时，才会对该位置进行处理。

  • 这意味着只有尚未被访问过的位置才会被赋值。

  • 一旦某个位置被访问过（即height[x][y]被赋值为非-1的值），它就不会再次进入队列。

• 为什么不会重复赋值

  • 假设某个位置(x, y)在第一次扩展时被赋值为height[a][b] + 1，那么height[x][y]就不再是-1。

  • 在后续的扩展中，当再次检查(x, y)时，height[x][y] == -1这个条件已经不满足，因此不会再次赋值。

  • 这保证了每个位置的高度只被赋值一次。

4.代码实现

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();//vector<vector<bool>> vis(m, vector<bool>(n));vector<vector<int>> height(m, vector<int>(n, -1));queue<pair<int, int>> q;for(int i = 0; i < m; i++){for(int j = 0; j < n; j++){if(isWater[i][j] == 1){height[i][j] = 0;q.push({i, j});}}}while(q.size()){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 && height[x][y] == -1){height[x][y] = height[a][b] + 1;q.push({x, y});}}}return height;}
};

4.地图分析

1162. 地图分析 - 力扣（LeetCode）

1.题目解析

你现在手里有一份大小为 n x n 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地。

请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的，并返回该距离。如果网格上只有陆地或者海洋，请返回 -1。

我们这里说的距离是「曼哈顿距离」（ Manhattan Distance）：(x0, y0) 和 (x1, y1) 这两个单元格之间的距离是 |x0 - x1| + |y0 - y1| 。

2.示例

示例 1：

输入：grid = [[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大，最大距离为 2。

示例 2：

输入：grid = [[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释： 
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。

3.解题思路

1.什么是曼哈顿距离？

 

4.代码实现

 

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();vector<vector<int>> dist(m, vector<int>(n, -1));queue<pair<int, int>> q;int ret = -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});}while(q.size()){auto [a, b] = q.front();q.pop();for(int k = 0; k < 4; k++){int x = a +dx[k], y = b + dy[k];if(x >= 0 && y >= 0 && x < m && 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;}
};