LeetCode题解 - BFS算法

- 日理万妓 2023-01-19 10:59 12阅读 0赞

# BFS算法 #

### 文章目录 ###

*  BFS算法
 *   *  一、算法框架
     *  二、LeetCode题目详解
     *   *  111. 二叉树的最小深度（简单）
         *  1091. 二进制矩阵中的最短路径
         *  752. 打开转盘锁（中等）
         *  127. 单词接龙（困难）
     *  三、双向BFS优化（后续再看）

--------------------

讲解部分参考：作者：labuladong 公众号：labuladong

BFS 的核心思想应该不难理解的，就是把一些问题抽象成图，从一个点开始，向四周开始扩散。一般来说，我们写 BFS 算法都是用「队列」这种数据结构，每次将一个节点周围的所有节点加入队列。

BFS 相对 DFS 的最主要的区别是：**BFS 找到的路径一定是最短的，但代价就是空间复杂度比 DFS 大很多**

## 一、算法框架 ##

要说框架的话，我们先举例一下 BFS 出现的常见场景好吧，**问题的本质就是让你在一幅「图」中找到从起点`start`到终点`target`的最近距离，这个例子听起来很枯燥，但是 BFS 算法问题其实都是在干这个事儿。**

这个广义的描述可以有各种变体，比如走迷宫，有的格子是围墙不能走，从起点到终点的最短距离是多少？如果这个迷宫带「传送门」可以瞬间传送呢？

再比如说两个单词，要求你通过某些替换，把其中一个变成另一个，每次只能替换一个字符，最少要替换几次？

再比如说连连看游戏，两个方块消除的条件不仅仅是图案相同，还得保证两个方块之间的最短连线不能多于两个拐点。你玩连连看，点击两个坐标，游戏是如何判断它俩的最短连线有几个拐点的？

再比如……

净整些花里胡哨的，这些问题都没啥奇技淫巧，本质上就是一幅「图」，让你从一个起点，走到终点，问最短路径。这就是 BFS 的本质，框架搞清楚了直接默写就好。记住下面这个框架就 OK 了：

// 计算从起点 start 到终点 target 的最近距离
    int BFS(Node start, Node target) {
        
        Queue<Node> q; // 核心数据结构
        Set<Node> visited; // 避免走回头路
    
        q.offer(start); // 将起点加入队列
        visited.add(start);
        int step = 0; // 记录扩散的步数
    
        while (!q.isEmpty()) {
        
            int sz = q.size();
            /* 将当前队列中的所有节点向四周扩散 */
            for (int i = 0; i < sz; i++) {
        
                Node cur = q.poll();
                /* 划重点：这里判断是否到达终点 */
                if (cur is target)
                    return step;
                /* 将 cur 的相邻节点加入队列 */
                for (Node x : cur.adj())
                    if (x not in visited) {
        
                        q.offer(x);
                        visited.add(x);
                    }
            }
            /* 划重点：更新步数在这里 */
            step++;
        }
    }

队列`q`就不说了，BFS 的核心数据结构；`cur.adj()`泛指`cur`相邻的节点，比如说二维数组中，`cur`上下左右四面的位置就是相邻节点；`visited`的主要作用是防止走回头路，大部分时候都是必须的，但是像一般的二叉树结构，没有子节点到父节点的指针，不会走回头路就不需要`visited`。

## 二、LeetCode题目详解 ##

### 111. 二叉树的最小深度（简单） ###

给定一个二叉树，找出其最小深度。最小深度是从根节点到最近叶子节点的最短路径上的节点数量。\*\*说明：\*\*叶子节点是指没有子节点的节点。  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-OElrkdu0-1620612528900)(C:\\Users\\lp\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210510085251367.png)\]][img-OElrkdu0-1620612528900_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210510085251367.png]

输入：root = [3,9,20,null,null,15,7]
    输出：2

怎么套到 BFS 的框架里呢？首先明确一下起点`start`和终点`target`是什么，怎么判断到达了终点？

**显然起点就是`root`根节点，终点就是最靠近根节点的那个「叶子节点」嘛**，叶子节点就是两个子节点都是`null`的节点：

那么，按照我们上述的框架稍加改造来写解法即可：

int minDepth(TreeNode root) {
        
        if (root == null) return 0;
        Queue<TreeNode> q = new LinkedList<>();
        q.offer(root);
        // root 本身就是一层，depth 初始化为 1
        int depth = 1;
    
        while (!q.isEmpty()) {
        
            int sz = q.size();
            /* 将当前队列中的所有节点向四周扩散 */
            for (int i = 0; i < sz; i++) {
        
                TreeNode cur = q.poll();
                /* 判断是否到达终点 */
                if (cur.left == null && cur.right == null) 
                    return depth;
                /* 将 cur 的相邻节点加入队列 */
                if (cur.left != null)
                    q.offer(cur.left);
                if (cur.right != null) 
                    q.offer(cur.right);
            }
            /* 这里增加步数 */
            depth++;
        }
        return depth;
    }

--------------------

### 1091. 二进制矩阵中的最短路径 ###

给你一个 `n x n` 的二进制矩阵 `grid` 中，返回矩阵中最短 **畅通路径** 的长度。如果不存在这样的路径，返回 `-1` 。二进制矩阵中的 畅通路径 是一条从 **左上角** 单元格（即，`(0, 0)`）到 右下角 单元格（即，`(n - 1, n - 1)`）的路径，该路径同时满足下述要求：

*  路径途经的所有单元格都的值都是 `0` 。
 *  路径中所有相邻的单元格应当在 **8 个方向之一** 上连通（即，相邻两单元之间彼此不同且共享一条边或者一个角）。

**畅通路径的长度** 是该路径途经的单元格总数。  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-K60mqmCT-1620612528902)(C:\\Users\\lp\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210510090620475.png)\]][img-K60mqmCT-1620612528902_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210510090620475.png]

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

class Solution {
        
        public int shortestPathBinaryMatrix(int[][] grid) {
        
            if(grid == null || grid.length == 0 || grid[0].length == 0){
        
                return -1;
            }
             // 如果起点就阻塞那就玩完啦
            if(grid[0][0] == 1){
        
                return -1;
            }
            int[][] directions = {
        {
        -1, -1}, {
        -1, 0}, {
        -1, 1}, {
        0, 1}, {
        1, 1}, {
        1, 0}, {
        1, -1}, {
        0, -1}};//定义 8个方向
            //bfs的老套路 来个队列,数据结构为数组int[]
            Queue<int[]> queue = new LinkedList<>();
            int m = grid.length, n = grid[0].length;
            queue.add(new int[]{
        0, 0});//把起点扔进去
            grid[0][0] = 1;// 因为从出发点开始找寻路径，所以出发点不能再被经过，将其设为1
            int step = 1;
            
    
            while(!queue.isEmpty()){
        
                int sz = queue.size();
                for(int i = 0; i < sz; i++){
          // 依次取出队列的每个节点并进行遍历
                    int[] cur = queue.poll();
                    // 如果等于终点则返回
                    if(cur[0] == m - 1 && cur[1] == n - 1){
        
                        return step;
                    }
    				// 对于当前节点，对其8个方向进行搜寻
                    for(int[] d : directions){
        
                        int row = cur[0] + d[0];
                        int col = cur[1] + d[1];//当前节点的某个方向上的节点坐标
                       // 如果搜寻范围越界或者被堵住或者被已经被经历过，则跳过该方向，对下一个方向进行搜索
                        // grid[row][col] 为1有两种情况：1.网格初始化时就被设置为1，无法被经历 
            			//                            2.在之前的某次搜索过程中已经被经历过，则不用再次经历它
                        if(row < 0 || row >= m || col < 0 || col >= n || grid[row][col] == 1){
        
                            continue;
                        }
                        queue.add(new int[]{
        row, col});//将该节点加入队列，用于下一层的节点的搜索
                        grid[row][col] = 1;// 某方向的节点被经历过后，将其标记为1，以后不再经过它
                    }
                }
                 step++;// 一轮队列遍历完以后，即节点周围的一层节点被遍历完以后，路径长度+1
            }
            return -1;      
        }
    }

--------------------

### 752. 打开转盘锁（中等） ###

你有一个带有四个圆形拨轮的转盘锁。每个拨轮都有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`和`target`的限制，就思考一个问题：如果让你设计一个算法，穷举所有可能的密码组合，你怎么做**？从 `0000`开始搜索。对于每一个状态，它可以扩展到最多 8 个状态，即将它的第 `i = 0, 1, 2, 3`位增加 1 或减少 1，比如说从`"0000"`开始，转一次，可以穷举出`"1000", "9000", "0100", "0900"...`共 8 种密码。然后，再以这 8 种密码作为基础，对每个密码再转一下，穷举出所有可能…

**仔细想想，这就可以抽象成一幅图，每个节点有 8 个相邻的节点**，又让你求最短距离，这不就是典型的 BFS 嘛，框架就可以派上用场了

class Solution {
        
        public int openLock(String[] deadends, String target) {
        
            // 用哈希表记录需要跳过的死亡密码
           Set<String> dead = new HashSet<>();
           for(String d : deadends) dead.add(d);
           Queue<String> queue = new LinkedList<>();
           Set<String> visited = new HashSet<>();// 记录已经穷举过的密码，防止走回头路
    		// 从起点开始启动广度优先搜索
           queue.offer("0000");
           visited.add("0000");
           int step = 0;
    
           while(!queue.isEmpty()){
        
               int sz = queue.size();
               for(int i = 0; i < sz; i++){
        
                   String cur = queue.poll();
                    if(dead.contains(cur)){
        
                        continue;
                    }
                   /* 判断是否到达终点 */
                    if(cur.equals(target)){
        
                        return step;
                    }
    				/* 将一个节点的未遍历相邻节点加入队列 */
                    for(int j = 0; j < 4; j++){
        
                        String up = plusOne(cur, j);
                        if(!visited.contains(up)){
        
                            queue.offer(up);
                            visited.add(up);
                        }
                        String down = minusOne(cur, j);
                        if(!visited.contains(down)){
        
                            queue.offer(down);
                            visited.add(down);
                        }
                    }
               }   
                step++; 
           }
            return -1;
        }
    	// 将 s[j] 向上拨动一次
        public String plusOne(String cur, int j){
        
            char[] ch = cur.toCharArray();
            if(ch[j] == '9'){
        
                ch[j] = '0';
            }else{
        
                ch[j] += 1;
            }
            return new String(ch);
        }
    	// 将 s[i] 向下拨动一次
        public String minusOne(String cur, int j){
        
            char[] ch = cur.toCharArray();
            if(ch[j] == '0'){
        
                ch[j] = '9';
            }else{
        
                ch[j] -= 1;
            }
            return new String(ch);
        }
    }

--------------------

### 127. 单词接龙（困难） ###

字典 `wordList` 中从单词 `beginWord` 和 `endWord` 的 **转换序列** 是一个按下述规格形成的序列：

*  序列中第一个单词是 `beginWord` 。
 *  序列中最后一个单词是 `endWord` 。
 *  每次转换只能改变一个字母。
 *  转换过程中的中间单词必须是字典 `wordList` 中的单词。

给你两个单词 `beginWord` 和 `endWord` 和一个字典 `wordList` ，找到从 `beginWord` 到 `endWord` 的 **最短转换序列** 中的 **单词数目** 。如果不存在这样的转换序列，返回 0。

输入：beginWord = "hit", endWord = "cog", wordList = ["hot","dot","dog","lot","log","cog"]
    输出：5
    解释：一个最短转换序列是 "hit" -> "hot" -> "dot" -> "dog" -> "cog", 返回它的长度 5。

class Solution {
        
        public int ladderLength(String beginWord, String endWord, List<String> wordList) {
        
             // 第 1 步：先将 wordList 放到哈希表里，便于判断某个单词是否在 wordList 里
            Set<String> wordSet = new HashSet<>();
            for(String w: wordList){
        
                wordSet.add(w);
            }
             // 第 2 步：图的广度优先遍历，必须使用队列和表示是否访问过的 visited 哈希表
            if (beginWord.equals(endWord))return 1;
            Queue<String> q = new ArrayDeque<>();
            Set<String> visited = new HashSet<>();
            q.offer(beginWord);
            visited.add(beginWord);//将初始单词加入
    
            // 第 3 步：开始广度优先遍历，包含起点，因此初始化的时候步数为 1
            int step = 1;  
    		while (!q.isEmpty()) {
        
    			int size = q.size();
    			for (int i = 0; i < size; i++) {
        
                    // 依次遍历当前队列中的单词
    				String cur = q.poll(); 
    				if (cur.equals(endWord))
    					return step;
    				// To find neighbours
    				List<String> neighbors = getNeighbors(cur.toCharArray(),wordSet); 
                    //如果 cur 修改 1 个字符后的邻居与 endWord 相同，则添加到队列与visited中
    				for (String nei : neighbors) {
        
    					if (!visited.contains(nei)) {
        
    						q.offer(nei);
    						visited.add(nei);
    					}
    				}
    			}
    			step++;
    		}
    		return 0;
        }
        private List<String> getNeighbors(char[] currentWord, Set<String> wordSet) {
        
    		List<String> res = new ArrayList<>();
            //尝试对 currentWord 修改每一个字符，看看是不是能与 endWord 匹配
    		for (int i = 0; i < currentWord.length; i++) {
        
    			char orginialChar = currentWord[i]; // 先保存初始字符
    			for (char ch = 'a'; ch <= 'z'; ch++) {
        
    				if (ch == orginialChar)
    					continue;
    				currentWord[i] = ch;
    				String newString = new String(currentWord);
    				if(wordSet.contains(newString)) res.add(newString);
    			}
    			currentWord[i] = orginialChar;//恢复初始字符，接着判断下一个字符
    		}
    		return res;
    	}
    }

此题可以使用双向BFS进行优化，后续有时间再看，先掌握基本的BFS框架

## 三、双向BFS优化（后续再看） ##

**传统的 BFS 框架就是从起点开始向四周扩散，遇到终点时停止；而双向 BFS 则是从起点和终点同时开始扩散，当两边有交集的时候停止**。

为什么这样能够能够提升效率呢？其实从 Big O 表示法分析算法复杂度的话，它俩的最坏复杂度都是`O(N)`，但是实际上双向 BFS 确实会快一些，我给你画两张图看一眼就明白了：  
![\[外链图片转存失败,源站可能有防盗链机制,建议将图片保存下来直接上传(img-ytGpSXLS-1620612528903)(C:\\Users\\lp\\AppData\\Roaming\\Typora\\typora-user-images\\image-20210510095956201.png)\]][img-ytGpSXLS-1620612528903_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210510095956201.png]  
图示中的树形结构，如果终点在最底部，按照传统 BFS 算法的策略，会把整棵树的节点都搜索一遍，最后找到`target`；而双向 BFS 其实只遍历了半棵树就出现了交集，也就是找到了最短距离。从这个例子可以直观地感受到，双向 BFS 是要比传统 BFS 高效的。

**不过，双向 BFS 也有局限，因为你必须知道终点在哪里**。比如我们刚才讨论的二叉树最小高度的问题，你一开始根本就不知道终点在哪里，也就无法使用双向 BFS；但是第二个密码锁的问题，是可以使用双向 BFS 算法来提高效率的，代码稍加修改即可：

int openLock(String[] deadends, String target) {
        
        Set<String> deads = new HashSet<>();
        for (String s : deadends) deads.add(s);
        // 用集合不用队列，可以快速判断元素是否存在
        Set<String> q1 = new HashSet<>();
        Set<String> q2 = new HashSet<>();
        Set<String> visited = new HashSet<>();
    
        int step = 0;
        q1.add("0000");
        q2.add(target);
    
        while (!q1.isEmpty() && !q2.isEmpty()) {
        
            // 哈希集合在遍历的过程中不能修改，用 temp 存储扩散结果
            Set<String> temp = new HashSet<>();
    
            /* 将 q1 中的所有节点向周围扩散 */
            for (String cur : q1) {
        
                /* 判断是否到达终点 */
                if (deads.contains(cur))
                    continue;
                if (q2.contains(cur))
                    return step;
                visited.add(cur);
    
                /* 将一个节点的未遍历相邻节点加入集合 */
                for (int j = 0; j < 4; j++) {
        
                    String up = plusOne(cur, j);
                    if (!visited.contains(up))
                        temp.add(up);
                    String down = minusOne(cur, j);
                    if (!visited.contains(down))
                        temp.add(down);
                }
            }
            /* 在这里增加步数 */
            step++;
            // temp 相当于 q1
            // 这里交换 q1 q2，下一轮 while 就是扩散 q2
            q1 = q2;
            q2 = temp;
        }
        return -1;
    }

双向 BFS 还是遵循 BFS 算法框架的，只是**不再使用队列，而是使用 HashSet 方便快速判断两个集合是否有交集**。

另外的一个技巧点就是 **while 循环的最后交换`q1`和`q2`的内容**，所以只要默认扩散`q1`就相当于轮流扩散`q1`和`q2`。

其实双向 BFS 还有一个优化，就是在 while 循环开始时做一个判断：

// ...
    while (!q1.isEmpty() && !q2.isEmpty()) {
        if (q1.size() > q2.size()) {
            // 交换 q1 和 q2
            temp = q1;
            q1 = q2;
            q2 = temp;
        }
        // ...

为什么这是一个优化呢？

因为按照 BFS 的逻辑，队列（集合）中的元素越多，扩散之后新的队列（集合）中的元素就越多；在双向 BFS 算法中，如果我们每次都选择一个较小的集合进行扩散，那么占用的空间增长速度就会慢一些，效率就会高一些。

while 循环的最后交换`q1`和`q2`的内容\*\*，所以只要默认扩散`q1`就相当于轮流扩散`q1`和`q2`。

不过话说回来，**无论传统 BFS 还是双向 BFS，无论做不做优化，从 Big O 衡量标准来看，空间复杂度都是一样的**，只能说双向 BFS 是一种 trick 吧，掌握不掌握其实都无所谓。最关键的是把 BFS 通用框架记下来，反正所有 BFS 算法都可以用它套出解法。

[img-OElrkdu0-1620612528900_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210510085251367.png]: /images/20221021/dea005f37c7c4cc59b89e956a44a1db1.png
[img-K60mqmCT-1620612528902_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210510090620475.png]: /images/20221021/dd42888498964d94b82182e3387b0e05.png
[img-ytGpSXLS-1620612528903_C_Users_lp_AppData_Roaming_Typora_typora-user-images_image-20210510095956201.png]: /images/20221021/bfb0759e2a77401a995e8b01deff55f6.png