多源 BFS 算法详解与经典题目解析

多源 BFS

单源最短路：只有一个起点到终点的最短路问题。 多源最短路问题：有多个起点到终点的最短路问题。 多源 BFS：用 BFS 来解决边权相同的多源最短路问题。

解法：

1. 暴力解题，把多源最短路问题，转化为若干个单源最短路问题。
2. 把所有起点当成一个起点，问题就变成了单源最短路问题。

542. 01 矩阵

题目链接：542. 01 矩阵

题目描述：

题目解析：

• 给一个只有 0 1 的二维数组，计算其中每一个元素到 0 的最短距离，自己是 0 距离就是 0，将距离存入一个相同规模二维数组的下标中。

法一： 解题思路：

• 我们如果遍历数组，找到 1 后，就进行求该元素到 0 的最短距离。
• 求最短距离就使用前面求权值相同的最短距离的方法即可。
• 但是会超时。

解题代码：

//时间复杂度：O(M*N*M*N)//空间复杂度：O(M*N)
class Solution {
    int[] dx = {0, 0, 1, -1};
    int[] dy = {1, -1, 0, 0};
    int m, n;

    public int[][] updateMatrix(int[][] mat) {
        m = mat.length;
        n = mat[0].length;
        int[][] ret = new int[m][n];
        // 遍历 mat，遍历到 1 找最近的 0
        for (int i = 0; i < m; i++) {
            for (int j = ; j < n; j++) {
                 (mat[i][j] == ) {
                    ret[i][j] = ;
                }  {
                    ret[i][j] = bfs(mat, i, j);
                }
            }
        }
         ret;
    }

       {
        Queue<[]> queue =  <>();
        queue.add( []{x, y});
        [][] flag =  [m][n];
        flag[x][y] = ;
           ;
         (!queue.isEmpty()) {
            ret++;
               queue.size();
             (size-- != ) {
                [] arr = queue.poll();
                 (   ; i < ; i++) {
                       arr[] + dx[i];
                       arr[] + dy[i];
                    
                     (a >=  && a < m && b >=  && b < n && !flag[a][b] && mat[a][b] != ) {
                        flag[a][b] = ;
                        queue.add( []{a, b});
                    }
                    
                     (a >=  && a < m && b >=  && b < n && mat[a][b] == )  ret;
                }
            }
        }
         ;
    }
}