Leetcode——BFS在树和图结构中的运用

港控/mmm° 2022-10-29 13:29 147阅读 0赞

## pythons模板 ##

BFS 使用队列，把每个还没有搜索到的点依次放入队列，然后再弹出队列的头部元素当做当前遍历点。BFS 总共有两个模板：

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

while queue 不空：
        cur = queue.pop()
        for 节点 in cur的所有相邻节点：
            if 该节点有效且未访问过：
                queue.push(该节点)

但是用 BFS 来求最短路径的话，以上这个框架还需要稍微修改一下。

如果用上面这种写法来遍历的话，**我们是无法区分 BFS 遍历中的每一“层”的**。这是因为，遍历的时候，第 1 层的结点还没出完队列，第 2 层的结点就进来了。这个队列中第 1 层和第 2 层的结点会紧挨在一起，无法区分，也就无法知道每个结点的距离 depth 了。  
因此，我们需要稍微修改一下代码，在每一层遍历开始前，记录队列中的结点数量 n ，然后一口气处理完这一层的 n 个结点 。(通过每次对队列的长度进行计算，再进行循环，实现逐层)这样，我们就知道这 n个结点位于同一层了。然后遍历下一层的时候，把变量 depth 加一。代码框架是这样的：

level = 0
    depth = 0 # 记录遍历到第几层
    while queue 非空:
        depth++
        n = queue 中的元素个数
        循环 n 次:
            node = queue.pop()
            for node 的所有相邻结点 m:
                if m 未访问过:
                    queue.push(m)

## 最短路径例题 ##

[102. 二叉树的层序遍历][102.]  
如果我们的地图上只有陆地或者海洋，请返回 -1。  
这道题就是一个在网格结构中求最短路径的问题。同时，它也是一个「岛屿问题」，即用网格中的 1 和 0 表示陆地和海洋，模拟出若干个岛屿。其中将遍历过的格子标记为 2，**避免重复遍历**。

class Solution:
        def maxDistance(self, grid: List[List[int]]) -> int:
            N = len(grid)
            queue = []
            for i in range(N):
                for j in range(N):
                    if grid[i][j] == 1:
                        queue.append((i,j))
            if len(queue) == 0 or len(queue) == N*N:
                return -1
            distance = -1
            while len(queue) >0:
                distance += 1
                M = len(queue)
                for i in range(M):
                    r,c = queue.pop(0)
                    #上面
                    if c-1>=0 and grid[r][c-1] == 0:
                        queue.append((r,c-1))
                        grid[r][c-1] = 2
                    #左边
                    if r-1>=0 and grid[r-1][c] == 0:
                        queue.append((r-1,c))
                        grid[r-1][c] = 2
                    #右边
                    if r+1<N and grid[r+1][c] == 0:
                        queue.append((r+1,c))
                        grid[r+1][c] = 2
                    #下面
                    if c+1<N and grid[r][c+1] == 0:
                        queue.append((r,c+1))
                        grid[r][c+1] = 2
    
            return distance

class Solution:
        def maxDistance(self, grid: List[List[int]]) -> int:
            n = len(grid)
            steps = -1
            queue = [(i, j) for i in range(n) for j in range(n) if grid[i][j] == 1]
            if len(queue) == 0 or len(queue) == n ** 2: return steps
            while len(queue) > 0:
                for _ in range(len(queue)): 
                    x, y = queue.pop(0)
                    for xi, yj in [(x + 1, y), (x - 1, y), (x, y + 1), (x, y - 1)]:
                        if xi >= 0 and xi < n and yj >= 0 and yj < n and grid[xi][yj] == 0:
                            queue.append((xi, yj))
                            grid[xi][yj] = -1
                steps += 1
                    
            return steps

[542. 01 矩阵][542. 01]

对于本题是可以直接修改原数组 seen 来记录距离和标志是否访问的，这里要注意先把 matrix 数组中 1 的位置设置成 -1

class Solution:
        def updateMatrix(self, matrix: List[List[int]]) -> List[List[int]]:
            m, n = len(matrix), len(matrix[0])
            dist = [[0] * n for _ in range(m)]
            zeroes_pos = [(i, j) for i in range(m) for j in range(n) if matrix[i][j] == 0]
            # 将所有的 0 添加进初始队列中
            q = collections.deque(zeroes_pos)
            seen = set(zeroes_pos)
    
            # 广度优先搜索
            while q:
                i, j = q.popleft()
                for ni, nj in [(i - 1, j), (i + 1, j), (i, j - 1), (i, j + 1)]:
                    if 0 <= ni < m and 0 <= nj < n and (ni, nj) not in seen:
                        dist[ni][nj] = dist[i][j] + 1
                        q.append((ni, nj))
                        seen.add((ni, nj))
            
            return dist

[102.]: https://leetcode-cn.com/problems/binary-tree-level-order-traversal/solution/bfs-de-shi-yong-chang-jing-zong-jie-ceng-xu-bian-l/
[542. 01]: https://leetcode-cn.com/problems/01-matrix/solution/