BFS 通用模板

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  = 1
    n = 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, 水标记为 -1
        manhattan = [[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] = 0
                        q.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, 地标记为 -1
        ans = [[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;
    }
}

这篇好文章是转载于：学新通技术网