广度优先遍历（思路）

841. 钥匙和房间

知识点：图；递归；BFS

题目描述

有 N 个房间，开始时你位于 0 号房间。每个房间有不同的号码：0，1，2，…，N-1，并且房间里可能有一些钥匙能使你进入下一个房间。

在形式上，对于每个房间 i 都有一个钥匙列表 rooms[i]，每个钥匙 rooms[i][j] 由 [0,1，…，N-1] 中的一个整数表示，其中 N = rooms.length。 钥匙 rooms[i][j] = v 可以打开编号为 v 的房间。

最初，除 0 号房间外的其余所有房间都被锁住。

你可以自由地在房间之间来回走动。

如果能进入每个房间返回 true，否则返回 false。

示例

输入: [[1],[2],[3],[]]
输出: true
解释:  
我们从 0 号房间开始，拿到钥匙 1。
之后我们去 1 号房间，拿到钥匙 2。
然后我们去 2 号房间，拿到钥匙 3。
最后我们去了 3 号房间。
由于我们能够进入每个房间，我们返回 true。

输入：[[1,3],[3,0,1],[2],[0]]
输出：false
解释：我们不能进入 2 号房间。

解法一：广度优先(BFS)

广度优先的意思就是我们不拿到一个钥匙走到头了，我们一个房间一个房间的进，拿到第一个房间的钥匙，把第一个房间里的钥匙对应的门都打开，然后再去第二个房间。这样一个一个的进。

class Solution {
    //标志位就是防止被重复遍历；
    //设置0号访问过，为了防止节点多次入队，需要在入队前将其设置为已访问；
    //0号房间入队；
    //没有被访问过；
    //保证入队的都是没有被遍历过的；
           
}

体会

• 1.只要是广度优先的，肯定要用队列，天然是在一起的。 一边弹出，一边遍历，弹出一个以后，就把它的孩子或者是它的关联入队，保证把这一层，或这个节点的都弹出了，接着继续弹下一层或者下一个节点的。

• 2.树的BFS：先把root节点入队，然后再一层一层的遍历。
  图的BFS也是一样的，与树的BFS的区别是：

  • 1.树只有一个root，而图可以有多个源点，所有首先需要将多个源点入队。
  • 2.树是有向的因此不需要标志是否访问过，而对于无向图而言，必须得标志是否访问过！并且为了防止某个节点多次入队，需要在入队前将其设置为已访问！

• 3.树用DFS比较多，图用BFS比较多；

133. 克隆图

知识点：图；递归;BFS

题目描述

给你无向 连通 图中一个节点的引用，请你返回该图的 深拷贝（克隆）。

图中的每个节点都包含它的值 val（int） 和其邻居的列表（list[Node]）。

class Node {
    public int val;
    public List<Node> neighbors;
}

示例

输入：adjList = [[2,4],[1,3],[2,4],[1,3]]
输出：[[2,4],[1,3],[2,4],[1,3]]
解释：
图中有 4 个节点。
节点 1 的值是 1，它有两个邻居：节点 2 和 4 。
节点 2 的值是 2，它有两个邻居：节点 1 和 3 。
节点 3 的值是 3，它有两个邻居：节点 2 和 4 。
节点 4 的值是 4，它有两个邻居：节点 1 和 3 。

输入：adjList = [[]]
输出：[[]]
解释：输入包含一个空列表。该图仅仅只有一个值为 1 的节点，它没有任何邻居。

输入：adjList = []
输出：[]
解释：这个图是空的，它不含任何节点。

输入：adjList = [[2],[1]]
输出：[[2],[1]]

解法一：广度优先(BFS)

和深度一样需要有个map来判断是否遍历过了，使用BFS，创建一个队列，然后将各节点依次入队。入队头节点，然后取出，遍历出队的邻居节点，如果没有被访问过，那就入队，克隆并且添加到map中，如果访问过了，那就更新克隆节点的邻居节点就可以了。

 
// Definition for a Node.
class Node {
    public int val;
    public List<Node> neighbors;
    public Node() {
        val = 0;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val) {
        val = _val;
        neighbors = new ArrayList<Node>();
    }
    public Node(int _val, ArrayList<Node> _neighbors) {
        val = _val;
        neighbors = _neighbors;
    }
}
 

class Solution {
         //首节点入队；
         //克隆节点并入表；
         //依次设置访问过并入队；
         //添加邻居，注意是添加的克隆的；
      
}

1162. 地图分析

知识点：图；递归

题目描述

你现在手里有一份大小为 N x N 的 网格 grid，上面的每个 单元格 都用 0 和 1 标记好了。其中 0 代表海洋，1 代表陆地，请你找出一个海洋单元格，这个海洋单元格到离它最近的陆地单元格的距离是最大的。

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

如果网格上只有陆地或者海洋，请返回 -1。

示例

输入：[[1,0,1],[0,0,0],[1,0,1]]
输出：2
解释： 
海洋单元格 (1, 1) 和所有陆地单元格之间的距离都达到最大
最大距离为 2。

输入：[[1,0,0],[0,0,0],[0,0,0]]
输出：4
解释： 
海洋单元格 (2, 2) 和所有陆地单元格之间的距离都达到最大，最大距离为 4。

解法一：广度优先(BFS)

树的BFS：先把root节点入队，然后再一层一层的遍历。
图的BFS也是一样的，与树的BFS的区别是：
1.树只有一个root，而图可以有多个源点，所有首先需要将多个源点入队。
2.树是有向的因此不需要标志是否访问过，而对于无向图而言，必须得标志是否访问过！并且为了防止某个节点多次入队，需要在入队前将其设置为已访问！

树的广度优先搜索：从root开始往子节点上；
一个源点的广度优先和多个源点的广度优先，参考下面链接 广度优先搜索

这道题目就是多源广度优先搜索的样题，我们寻找离陆地最远的海洋单元格，可以将其转化为从所有的陆地开始一轮一轮的往外扩，最后的就是最远的。
第一轮变化以各个陆地为起点，走一格就能到达的海域；第二轮变化是在第一轮的基础上走两格能到达的海域，这样子不断变化，越到后面没有被覆盖的海域离陆地的距离最远，也越接近我们想找到的那个海域，直到地图被全覆盖。

class Solution {
   
            //把所有的陆地先入队；
            //设置四个变化方向；
        
            //没有陆地或海洋；
            //从各个陆地一圈一圈向外扩，最后就是最远的；
            //出队点；
         
            //求出此坐标的四个相邻坐标；
            //剔除无效坐标和周围陆地；
            //向外扩；
            //返回最后一次出队的坐标点；
    
}

解法二 ：

• 格子 (r, c) 的相邻四个格子为：(r-1, c)、(r+1, c)、(r, c-1) 和 (r, c+1)；
• 使用函数 inArea 判断当前格子的坐标是否在网格范围内；
• 将遍历过的格子标记为 2，避免重复遍历。

对于网格结构的性质、网格结构的 DFS 遍历技巧不是很了解的同学，可以复习一下上一篇文章：LeetCode 例题精讲 | 12 岛屿问题：网格结构中的 DFS。

上一篇文章讲过了网格结构 DFS 遍历，这篇文章正好讲解一下网格结构的 BFS 遍历。要解最短路径问题，我们首先要写出层序遍历的代码，仿照上面的二叉树层序遍历代码，类似地可以写出网格层序遍历：

// 网格结构的层序遍历
// 从格子 (i, j) 开始遍历
void bfs(int[][] grid, int i, int j) {
    Queue<int[]> queue = new ArrayDeque<>();
    queue.add(new int[]{r, c});
    while (!queue.isEmpty()) {
        int n = queue.size();
        for (int i = 0; i < n; i++) { 
            int[] node = queue.poll();
            int r = node[0];
            int c = node[1];
            if (r-1 >= 0 && grid[r-1][c] == 0) {
                grid[r-1][c] = 2;
                queue.add(new int[]{r-1, c});
            }
            if (r+1 < N && grid[r+1][c] == 0) {
                grid[r+1][c] = 2;
                queue.add(new int[]{r+1, c});
            }
            if (c-1 >= 0 && grid[r][c-1] == 0) {
                grid[r][c-1] = 2;
                queue.add(new int[]{r, c-1});
            }
            if (c+1 < N && grid[r][c+1] == 0) {
                grid[r][c+1] = 2;
                queue.add(new int[]{r, c+1});
            }
        }
    }
}

以上的层序遍历代码有几个注意点：

• 队列中的元素类型是 int[] 数组，每个数组的长度为 2，包含格子的行坐标和列坐标。
• 为了避免重复遍历，这里使用到了和 DFS 遍历一样的技巧：把已遍历的格子标记为 2。注意：我们在将格子放入队列之前就将其标记为 2。想一想，这是为什么？
• 在将格子放入队列之前就检查其坐标是否在网格范围内，避免将「不存在」的格子放入队列。

这段网格遍历代码还有一些可以优化的地方。由于一个格子有四个相邻的格子，代码中判断了四遍格子坐标的合法性，代码稍微有点啰嗦。我们可以用一个 moves 数组存储相邻格子的四个方向：

int[][] moves = {
    {-1, 0}, {1, 0}, {0, -1}, {0, 1},
};

然后把四个 if 判断变成一个循环：

for (int[][] move : moves) {
    int r2 = r + move[0];
    int c2 = c + move[1];
    if (inArea(grid, r2, c2) && grid[r2][c2] == 0) {
        grid[r2][c2] = 2;
        queue.add(new int[]{r2, c2});
    }
}

写好了层序遍历的代码，接下来我们看看如何来解决本题中的最短路径问题。

这道题要找的是距离陆地最远的海洋格子。假设网格中只有一个陆地格子，我们可以从这个陆地格子出发做层序遍历，直到所有格子都遍历完。最终遍历了几层，海洋格子的最远距离就是几。

从单个陆地格子出发的距离（动图）

那么有多个陆地格子的时候怎么办呢？一种方法是将每个陆地格子都作为起点做一次层序遍历，但是这样的时间开销太大。

BFS 完全可以以多个格子同时作为起点。我们可以把所有的陆地格子同时放入初始队列，然后开始层序遍历，这样遍历的效果如下图所示：

从多个陆地格子出发的距离

这种遍历方法实际上叫做「多源 BFS」。多源 BFS 的定义不是今天讨论的重点，你只需要记住多源 BFS 很方便，只需要把多个源点同时放入初始队列即可。

需要注意的是，虽然上面的图示用 1、2、3、4 表示层序遍历的层数，但是在代码中，我们不需要给每个遍历到的格子标记层数，只需要用一个 distance 变量记录当前的遍历的层数（也就是到陆地格子的距离）即可。

最终，我们得到的题解代码为：

 

 
  *// 将所有的陆地格子加入队列*
   

  *// 如果地图上只有陆地或者海洋，返回 -1*
 

 

   *// 记录当前遍历的层数（距离）*
 

*// 判断坐标 (r, c) 是否在网格中*
 

体会

树的BFS：先把root节点入队，然后再一层一层的遍历。
图的BFS也是一样的，与树的BFS的区别是：
1.树只有一个root，而图可以有多个源点，所有首先需要将多个源点入队。
2.树是有向的因此不需要标志是否访问过，而对于无向图而言，必须得标志是否访问过！并且为了防止某个节点多次入队，需要在入队前将其设置为已访问！

752. 打开转盘锁

知识点：图；BFS

题目描述

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有10个数字： ‘0’, ‘1’, ‘2’, ‘3’, ‘4’, ‘5’, ‘6’, ‘7’, ‘8’, ‘9’ 。每个拨轮可以自由旋转：例如把 ‘9’ 变为 ‘0’，’0′ 变为 ‘9’ 。每次旋转都只能旋转一个拨轮的一位数字。

锁的初始数字为 ‘0000’ ，一个代表四个拨轮的数字的字符串。

列表 deadends 包含了一组死亡数字，一旦拨轮的数字和列表里的任何一个元素相同，这个锁将会被永久锁定，无法再被旋转。

字符串 target 代表可以解锁的数字，你需要给出解锁需要的最小旋转次数，如果无论如何不能解锁，返回 -1 。

示例

输入：deadends = ["0201","0101","0102","1212","2002"], target = "0202"
输出：6
解释：
可能的移动序列为 "0000" -> "1000" -> "1100" -> "1200" -> "1201" -> "1202" -> "0202"。
注意 "0000" -> "0001" -> "0002" -> "0102" -> "0202" 这样的序列是不能解锁的，
因为当拨动到 "0102" 时这个锁就会被锁定。

输入: deadends = ["8888"], target = "0009"
输出：1
解释：
把最后一位反向旋转一次即可 "0000" -> "0009"。

输入: deadends = ["8887","8889","8878","8898","8788","8988","7888","9888"], target = "8888"
输出：-1
解释：
无法旋转到目标数字且不被锁定。

输入: deadends = ["0000"], target = "8888"
输出：-1

解法一：BFS

这道题目看起来很绕，其实透过这个场景去看本质，其实就是一幅图，什么意思呢，每个密码就可以看做是图的节点，目标就是找到target的节点，怎么办，遍历呗，啥时候找到啥时候停，而图的遍历自然要用到BFS，每个节点其实都有8个相邻节点，因为它转动后下一个可能的密码就是8个，举个例子，比如”0000″转一下以后”1000,9000,0100,0900,…”，这就是相邻节点；然后还有用一个visited来记录已经遍历过的，防止回头路，此外如果有密码等于deadend了，那就跳过不用遍历这个密码了。

BFS算法框架：

//计算起点start到终点target的最小距离
int BFS(Node start, Node target){ 
      //核心结构：队列；
      //在图中都会用到，因为存在着交叉，会走回头路，树中则不需要，因为有next指针；
      //起点入队；
       
      //记录扩散步数；
    
      //从当前队列中所有节点向与其关联的节点扩散；
         
      //注意不同题目里这里的判断条件，是否到达终点；
            
      //这里指的是当前节点的邻居节点；
      //还没走过再加入；不走回头路；
                 
      //注意在这里更新步数；
     
}

题解：

class Solution {
    
         
           //记录所有已经遍历到的密码；
         
             
           //截止条件；
                
           //处理相邻节点；一共8个；
                 
    
}

仔细看一下上述题解，基本上是和框架也就是模板是一样的，要注意灵活变通。

原作者：Curryxin

链接：www.cnblogs.com/Curryxin/p/…

参考链接：(LeetCode 例题精讲 | 13 BFS 的使用场景：层序遍历、最短路径问题 (qq.com))