【重难点算法】多源 BFS_多源bfs

单源与多源 BFS

单源 BFS 是从图中的某一点（源点）出发，向周围进行广度优先搜索，在搜索的过程中记录每一点到源点的距离。多源 BFS 是从多个源点同时开始进行广度优先搜索，通常需要记录在搜索过程中当前点距离最近的源点的距离。广度优先搜索是用队列来实现的，对于单源的问题，队列的初始化就是某一个单一源点；对于多源问题，队列的初始化就是多个源点。这也是单源和多源问题的唯一区别。

实例剖析

例题1 矩阵距离

矩阵距离

给定一个 01 矩阵，返回一个相同大小的矩阵 $dis$，其中 $dis[i][j]$ 表示 $(i,j)$ 位置距离最近的 1 的曼哈顿距离。

【分析】对于这样的一个 01 矩阵，我们选择从所有的 1 出发，通过广度优先搜索的方法来计算 $(i,j)$ 到最近的 1 的距离。在本问题中，如果 1 的个数仅有一个，那么就是单源 BFS 问题，否则就是多源 BFS 问题。

• 首先，我们定义一个答案数组用来记录到最近的 1 的距离，数组初始化为 -1；定义一个队列，用来存放矩阵中 1 的位置。
• 接着遍历矩阵，将矩阵中 1 的位置存放在队列中，并将当前位置的 dis 赋值为 1，毕竟 1 距离最近的 1 距离为 0 嘛。
• 然后从队列中的 1 的位置 $(i,j)$ 一层层的向外扩展到新的位置 $(x,y)$，如果新的位置之前没有到达过，那么更新 $dis[x][y]=dis[i][j]+1$，并将扩展到的位置 $(x,y)$ 作为新的 “1” 存入队列。重复本步骤，直至队列为空。
• 不知道大家是否会有这样的疑问：为什么上述步骤中的 $(x,y)$ 距离最近的 1 的距离 $dis[x][y]$ 有这样的等式？因为，“如果新的位置之前没有到达过” 这句话表名从其他 1 的位置出发还未到达这个新的位置 $(x,y)$，而从当前的 1 广搜到达了这个新的位置，所以有 $dis[x][y]=dis[i][j]+1$ 这样的计算 $(x,y)$ 到最近的 1 距离的计算公式。

【示例代码】

class Solution{
public:
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};
    
    vector<vector<int>> getNearest1Distance(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size();
        vector<vector<int>> dis(m, vector<int>(n, -1));
        quequ<pair<int, int>> que;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    que.push({i, j});
                    dis[i][j] = 0;
                }
            }
        }
        
        while (!que.empty()) {
            auto pr = que.front();
            que.pop();
            int i = pr.first, j = pr.second;
            for (int k = 0; k < 4; ++k) {
                int x = i + dirs[k][0];
                int y = j + dirs[k][1];
                if (x >= 0 && x < m && y >= 0 && y < n && dis[x][y] == -1) {
					dis[x][y] = dis[i][j] + 1;
                    que.push(make_pair(x, y));
                }
            }
        }
        
     	return dis;   
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34

例题2 地图分析

1162. 地图分析

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

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

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

【分析】本题就是统计 $(i,j)$ 到最近的 1 的距离，如果记录矩阵中 1 的位置的队列的大小为空或者为 $n\ast n$，则说明矩阵中全为 0 或者全为 1，直接返回 -1。

【示例代码】

class Solution {
public:
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};
    int maxDistance(vector<vector<int>>& grid) {
        int n = grid.size();
        vector<vector<int>> dis(n, vector<int>(n, -1));

        queue<pair<int, int>> que;
        for (int i = 0; i < n; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 1) {
                    que.push({i, j});
                    dis[i][j] = 0;
                }
            }
        }

        if (que.empty() || que.size() == n*n) {
            return -1;
        }

        int res = 0;
        while (!que.empty()) {
            auto pr = que.front();        // 避免 auto& [i, j] 的写法
            int i = pr.first, j = pr.second;
            que.pop();

            for (int k = 0; k < 4; ++k) {
                int x = i + dirs[k][0];
                int y = j + dirs[k][1];

                if (x >= 0 && x < n && y >= 0 && y < n && dis[x][y] == -1) {
                    dis[x][y] = dis[i][j] + 1;
                    que.push({x, y});
                    res = max(res, dis[x][y]);
                }
            }
        }
        return res;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41

例题3 腐烂的橘子

994. 腐烂的橘子

在给定的 m x n 网格 grid 中，每个单元格可以有以下三个值之一：

• 值 0 代表空单元格；
• 值 1 代表新鲜橘子；
• 值 2 代表腐烂的橘子。

每分钟，腐烂的橘子 周围 4 个方向上相邻 的新鲜橘子都会腐烂。

返回 直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1 。

【示例】

输入：grid = [[2,1,1],[1,1,0],[0,1,1]]
输出：4
1
2

在上述示例中，仅有一个烂橘子，那么该示例对应的就是单源 BFS 问题。一般情况下，该题是一个多源BFS问题。格子里有三种值分别代表不同的情况：

• 0 表示空格子；
• 1 表示格子中有新鲜的橘子；
• 2 表示格子中是烂橘子。

烂橘子每一秒会污染周围 4 方向上的新鲜橘子，并让其腐烂。我们要计算的是什么时候单元格中没有新鲜橘子了。

典型的多源广度优先搜索问题，我们从每一个烂橘子的单元格子出发，一圈一圈的污染周围四方向上的新鲜橘子，直到新鲜橘子的数量为 0。多源是多个源头的意思，这里代表的是多个烂橘子。使用广度优先算法解题，具体过程为：

• 首先遍历网格，使用队列记录存储烂橘子的位置坐标并统计新鲜橘子的数量 $cnt$。
• 接着从烂橘子的位置坐标出发，每次向外扩一圈到新位置 $(nx,ny)$，并更新新位置到最近的烂橘子的距离 $dist[nx][ny]$。因为每次向外扩一个单位距离，所以有 dist[nx][ny] = dist[x][y] + 1。
• 在向外扩展的过程中，如果 dist[nx][ny] = 1，即表明当前遇到了新鲜橘子，就将新鲜橘子数量减一，并更新 $ans = dis[nx][ny] $，如果 $cnt=0$ 则说明新鲜橘子已经全部被污染了，可以提前退出 $while$ 循环。
• 如果搜索结束后 $cnt>0$，说明有新鲜句子没被污染腐烂，返回 -1。

【示例代码】

class Solution {
    int cnt;        // 统计新鲜橘子的数量
    int dist[10][10];
    const int dirs[4][2] = {{-1, 0}, {1, 0}, {0, 1}, {0, -1}};

public:
    int orangesRotting(vector<vector<int>>& grid) {
        int m = grid.size(), n = grid[0].size(), ans = 0;
        memset(dist, -1, sizeof(dist));
        cnt = 0;

        queue<pair<int, int>> que;
        for (int i = 0; i < m; ++i) {
            for (int j = 0; j < n; ++j) {
                if (grid[i][j] == 2) {
                    que.push({i, j});
                    dist[i][j] = 0;
                }
                else if (grid[i][j] == 1) {
                    ++cnt;
                }
            }
        }

        while (!que.empty()) {
            pair<int, int> x = que.front();
            que.pop();
            for (int i = 0; i < 4; ++i) {
                int nx = x.first + dirs[i][0];
                int ny = x.second + dirs[i][1];
                // ~ 表示的是取反操作，-1取反是0，~dist[nx][ny] 如果 >= 0 表示已经访问过这个方格
                if (nx < 0 || nx >= m || ny < 0 || ny >= n || grid[nx][ny] == 0 || dist[nx][ny] > -1) {
                    continue;
                }
                dist[nx][ny] = dist[x.first][x.second] + 1;
                que.push(make_pair(nx, ny));
                if (grid[nx][ny] == 1) {
                    --cnt;
                    ans = dist[nx][ny];
                    if (cnt == 0) {
                        break;
                    }
                }
            }
        }

        return cnt ? -1: ans;
    }
};
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49