BFS 通用模板

模板"/>

BFS 通用模板

BFS 通用模板

• • DFS（深度优先搜索）和 BFS（广度优先搜索）
• 1162. 地图分析
• 1765. 地图中的最高点

Tree 的 BFS：要把 root 节点先入队，然后再一层一层的遍历。

DFS（深度优先搜索）和 BFS（广度优先搜索）

BFS 模板一：如果不需要确定当前遍历到了哪一层

while deque: # 非空node = deque.popleft()for m in node 的所有相邻结点:if m 未访问过:deque.append(m)

BFS 模板二：如果需要确定当前遍历到了哪一层

depth = 0 # 记录遍历到第几层
while queue 非空:depth += 1n = len(queue) for _ in range(n):node = queue.pop()for m in node 的所有相邻结点:if m 未访问过:queue.append(m)

图 与 Tree 的 BFS 区别：
1、tree 只有 1 个 root，而图可以是多源的，所以首先需要把多个源点加入队列。
2、tree 是有向的因此不需要标志是否访问过，而对于无向图来说，必须得标志是否访问过！防止某个节点多次入队。

1162. 地图分析

Leetcode

求所有海洋点到离它最近的陆地点的距离的最大值。
曼哈顿距离就是沿着横、竖到达另外一个点走的步数。

多源 BFS：

class Solution:def maxDistance(self, grid: List[List[int]]) -> int:# 模板一：n = len(grid)# 地先加入 q, 然后加入水，即先遍历完地后一圈一圈地遍历水。q = deque((i, j) for i in range(n) for j in range(n) if grid[i][j])# 地为 0, 水标记为 -1manhattan = [[v - 1 for v in row] for row in grid]while q:            i, j = q.popleft()for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):if (0 <= x < n and 0 <= y < n and manhattan[x][y] == -1):# 如果是水manhattan[x][y] = manhattan[i][j] + 1                       q.append((x, y)) # 加入水return x if (x := max(max(row) for row in manhattan)) else -1# 模板二：n, depth = len(grid), -1       q = deque((i, j) for i in range(n) for j in range(n) if grid[i][j])vis = [[v - 1 for v in row] for row in grid] # 0 表示已加入 q，即所有的地都已经访问过。while q:m = len(q)for _ in range(m): i, j = q.popleft()for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):if (0 <= x < n and 0 <= y < n and vis[x][y] == -1):vis[x][y] = 0q.append((x, y)) depth += 1 # 源点深度为 0 记录圈数return depth if depth else -1

class Solution {int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public int maxDistance(int[][] grid) {int n = grid.length, manhattan = -1;       int[][] vis = new int[n][n];for (int[] row : vis) Arrays.fill(row, -1);Deque<int[]> q = new ArrayDeque<>();for (int i = 0; i < n; i++){for (int j = 0; j < n; j++){if (grid[i][j] == 1){vis[i][j] = 0;q.offer(new int[]{i, j});}}}while (!q.isEmpty()){manhattan ++;int m = q.size();for (int i = 0; i < m; i++){int[] p = q.poll();for (int[] dir : dirs){int x = p[0] + dir[0], y = p[1] + dir[1];if (0 <= x && x < n && 0 <= y && y < n && vis[x][y] == -1) {vis[x][y] = 0;q.offer(new int[]{x, y});}}}            }return (manhattan == 0) ? -1 : manhattan;}
}

1765. 地图中的最高点

Leetcode
多源 Bfs，记录下所有水域的位置，然后从水域出发，广度优先搜索，计算出所有陆地格子的高度，即从每个水域格子向四周进行 BFS，每拓展一圈高度 + 1。

class Solution:def highestPeak(self, isWater: List[List[int]]) -> List[List[int]]:m, n = len(isWater), len(isWater[0]) # 水为 0, 地标记为 -1ans = [[v - 1 for v in row] for row in isWater]# 所有的水先加入 q （对应的 ans 为 0), 然后加入地,即先遍历完水后一圈一圈地遍历地。q = deque((i, j) for i in range(m) for j in range(n) if isWater[i][j])  while q:i, j = q.popleft() for x, y in ((i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)):                     if 0 <= x < m and 0 <= y < n and ans[x][y] == -1: ans[x][y] = ans[i][j] + 1  # 如果是地 ans[i][j]+1        q.append((x, y)) # 加入地return ans

class Solution {int[][] dirs = {{-1, 0}, {1, 0}, {0, -1}, {0, 1}};public int[][] highestPeak(int[][] isWater) {int m = isWater.length, n = isWater[0].length;int[][] high = new int[m][n];for (int[] row : high) Arrays.fill(row, -1); // -1 表示该格子尚未被访问过Deque<int[]> q = new ArrayDeque<>();for (int i = 0; i < m; ++i) {for (int j = 0; j < n; ++j) {if (isWater[i][j] == 1) {high[i][j] = 0;q.offer(new int[]{i, j}); // 将所有水域入队}}}while (!q.isEmpty()) {int[] p = q.poll();for (int[] dir : dirs) {int x = p[0] + dir[0], y = p[1] + dir[1];if (0 <= x && x < m && 0 <= y && y < n && high[x][y] == -1) {high[x][y] = high[p[0]][p[1]] + 1;q.offer(new int[]{x, y});}}}return high;}
}