轻松掌握广度优先搜索入门

轻松掌握广度优先搜索入门

轻松掌握广度优先搜索入门

广度优先遍历（BFS）是图的搜索算法之一，让我们直接进入主题，来感受一下它！

让我们明白广度的深意，大家是否玩过扫雷（权当大家玩过或者看别人玩过），当点击一个点以后，以这个点为中心，宛如水中落下石子一般荡漾开来，周围的点都会展开，这就像是广度优先搜索的搜索方式

再一个栗子！二叉树的是个容易在大脑中构建的模型，遍历二叉树的时候，如果是一层一层遍历，那么就是广度优先搜索（若是不断的从root一路往下到根，再回溯到上一级，这样的搜索是深度）

那么现在就让我们以题为例

力扣上面的一道题目 二叉树的最小深度

给定一个二叉树，找出其最小深度。

最小深度是从根节点到最近叶子节点的最短路径上的节点数量。

说明: 叶子节点是指没有子节点的节点。

示例:

给定二叉树 [3,9,20,null,null,15,7],

    3/ 9  20/  15   7

返回它的最小深度 2.

既然上面提到了二叉树，那么就以这题二叉树的最小深度为栗子开始讲解，看完题目，以我们人的思维来数，就是一眼看到最短的那个枝，数出来就可以完成，但是电脑无法如此直观的看到一整棵树，这个时候广度优先搜索派上了用场（这题亦可以用深度优先做，留在最后做扩展）

广度优先搜索是如何完成的呢，一层一层遍历，从上往下，如果发现当层存在一个节点，这个节点没有左右子节点，那么就表明它是叶子节点，则：它的深度就可以代表整棵树的最小深度

所以就是在广度搜索的过程中，判断每层的节点是否有子节点，在使用一个变量记录当前层数

上面我提到了广度搜索的过程， 必然是笔者特意安排的点，因为基础广度优先遍历是存在一个大体思路和模板的，既然是入门，那么就不说废话直接搬上这个模板给各位品尝！

		queue.offer( 初始化时符合条件的点 )while(queue.isNotEmpty){T cur = queue.poll();//这里做 根据cur做一些操作 If(cur的相邻点1符合条件){queue.offer(cur的相邻点1);}If(cur的相邻点2符合条件){queue.offer(cur的相邻点2);}...}

可能看着上面这个模板还是有点不通透，因为这个模板太通用了，要使用到这道题上面来还是需要改动，这里笔者给出完全符合这道题目的模板

	queue.offer( 树的根节点 )while(queue.isNotEmpty){int size = queue.size();for(int i = 0; i < size; i++){T cur = queue.poll();//这里判断cur是否有子节点，如果没有直接return;If(cur的左子节点不为空){queue.offer(cur.left);}If(cur的右子节点不为空){queue.offer(cur.right);}}}

进一步清晰模板以后，可以发现多了一个for循环，这个循环有何用呢?
先把上面题目里面的树的图拿下来，方便讲解

        3/ 9   20/    /  6   12 15  7

• 首先明确这里广度优先搜索的目的时最小深度，那么，如何判断和区分深度1（节点3）和深度2（节点9、20）以及深度3（节点15、7）之间的界限呢
• 就是通过这个for，这个for将一层的节点限制在一个for中，这个for的结束就代表一层以及被扫描完了
• 再细想想为何一个for代表一层
  • root节点（3）入队，这个时候进入while循环，队列大小为1，开始第一次for循环（也就是扫描深度1），然后俩个if条件将3的左节点9和有节点20放入队列
  • 接着第一个for结束，开始第二个for，这个时候队列大小为2，因为深度1的for把俩个节点放了进来，然后这个深度2的for，会遍历9和20的子节点，这个时候，深度2完成的时候，队列中会有4个点供深度3的for遍历（看着树的图也确实是深度3的节点有4个）
• 可以看的出来，利用队列FIFO的特性，和这个for完美的实现了一个for管理一层节点的功能

趁热打铁，上面说到需要一个变量来记录层数，那么我们可以在程序的开头初始化一个count变量，在每次for结束的时候做自增操作即可

那么现在我就贴上完整的AC代码：

/*** Definition for a binary tree node.* public class TreeNode {*     int val;*     TreeNode left;*     TreeNode right;*     TreeNode(int x) { val = x; }* }*/
import java.util.Queue;
import java.util.LinkedList;
class Solution {public int minDepth(TreeNode root) {if(root == null){return 0;}Queue<TreeNode> queue = new LinkedList<>();queue.offer(root);int level = 1;while(!queue.isEmpty()){int size = queue.size();for(int i = 0; i < size; i++){TreeNode cur = queue.poll();if(cur.left == null && cur.right == null){return level;}if(cur.left != null){queue.offer(cur.left);}if(cur.right != null){queue.offer(cur.right);}}level++;}return level;}
}

上面已经有了那么多的介绍，那么代码里面就不再出现注释了，如果你可以看懂这段代码，那么恭喜你，已经打开了广度优先搜索的大门！

马上打开第二题的广度优先搜索

腐烂的橘子

在给定的网格中，每个单元格可以有以下三个值之一：
在这里插入图片描述
值 0 代表空单元格；
值 1 代表新鲜橘子；
值 2 代表腐烂的橘子。
每分钟，任何与腐烂的橘子（在 4 个正方向上）相邻的新鲜橘子都会腐烂。
返回直到单元格中没有新鲜橘子为止所必须经过的最小分钟数。如果不可能，返回 -1。
示例 1：

输入：[[2,1,1],[1,1,0],[0,1,1]]
输出：4
示例 2：
输入：[[2,1,1],[0,1,1],[1,0,1]]
输出：-1
解释：左下角的橘子（第 2 行， 第 0 列）永远不会腐烂，因为腐烂只会发生在 4 个正向上。
示例 3：
输入：[[0,2]]
输出：0
解释：因为 0 分钟时已经没有新鲜橘子了，所以答案就是 0 。

为了更好的理解这道理，笔者不建议直接看本页面查看题目，而是可以点开上面题目名字的链接，去力扣刷题的界面查看题目，因为那里的排版更加清晰

先来聊聊这题的题意，每个腐烂的橘子在每一时刻，都可以感染周围的橘子（仅限方向 上、下、左、右），这里的腐烂的橘子像不像是扫雷的点亦或者是水中扔下的那个石子呢，是朝着四周荡漾开来似的感染！如果你想到了，那么恭喜你，明白了这题的解题思路是广度优先搜索

讨论几个点

• 初始符合条件的节点可能不止一个，不像二叉树必定只有一个root节点，而是一开始就可能存在多个腐烂的橘子
• 题目中描述的每分钟感染，那么，如果时刻1，有俩个腐烂的橘子，那么经过这俩个的感染，在时刻2会生成若干个腐烂的橘子，也就是时刻1的俩个和时刻2的若干个都必须作为一个整体来看待
• 时刻的计算，如果看完前俩点，这点就比较清晰了，因为有些类似于二叉树最小深度那题的深度，这里的时刻也是在for结束以后自增，但是这里还是存在一个小坑

好了，让我们看看这题的模板

	queue = ... queue.offer(所有腐烂的橘子坐标) 1.__________while(queue.isNotEmpty()){int size = queue.size();for(int i = 0; i < size; i++){T cur = queue.poll() ...//判断当前橘子的上下左右橘子是不是新鲜的，是：腐烂、入队，不是：就略过}2.______________}

模板中的

• 1.______处应该是声明count并且赋初值为0的位置
• 2.______处应该是count++的地方

如果真的这么做了，就会掉进一个小坑，试想，是否存在一种情况，使得队列中依然有元素，但是进入for以后没有任何符合条件的上下左右点，答：存在，即还有腐烂的橘子但是已经没有可达到的新鲜橘子被感染了，显然这种时候时刻不能自增，所以这个可以增加一个boolean变量flag赋予初始值false，仅当进入for循环以后发生一次以及一次以上更改的情况下，才把flag改为true，然后count自增的条件需要flag为true才可以

现在直接来看代码把

import java.util.Queue;
import java.util.LinkedList;
class Solution {//用于存放橘子坐标的类class Orange{int x;int y;public Orange(int x, int y){this.x = x;this.y = y;}}public int orangesRotting(int[][] grid) {//为了方便待会对四个方向进行遍历而存在的数组，预存四个方向的加减坐标int[] posx = new int[]{1, 0, -1, 0};int[] posy = new int[]{0, 1, 0, -1};int count = 0;//二维数组的俩个lenint len1 = grid.length;int len2 = grid[0].length;Queue<Orange> queue = new LinkedList();//初始遍历整个二维数组，找到所有腐烂的橘子作为第一次遍历的点for(int i = 0; i < len1; i++){for(int j = 0; j < len2; j++){if(grid[i][j] == 2){queue.offer(new Orange(i, j));}}}//开始whilewhile(!queue.isEmpty()){int size = queue.size();boolean flag = false;//一次for代表一个时刻for(int i = 0; i < size; i++){Orange cur = queue.poll();//遍历当前点的四个方向for(int j = 0; j < 4; j++){//判断四个方向的点是否符合条件，前四个是判断是否越界，//第五个条件是判断那个点是不是新鲜的橘子，若不是，则跳过if(cur.x + posx[j] < 0 || cur.x + posx[j] >= len1 || cur.y + posy[j] < 0 || cur.y + posy[j] >= len2 ||grid[cur.x + posx[j]][cur.y + posy[j]] != 1){continue;}//能够进入这里代表存在新鲜橘子可以感染，修改flagflag = true;//感染这个橘子grid[cur.x + posx[j]][cur.y + posy[j]] = 2;//把这个新的腐烂橘子入队queue.offer(new Orange(cur.x + posx[j], cur.y + posy[j]));}}//上面提到的flag觉得是否自增if(flag){count ++;}}//最后遍历一次数组，查看是狗存在新鲜橘子，因为可能存在对角线情况的新鲜橘子无法被感染boolean done = true;for(int i = 0; i < len1; i++){for(int j = 0; j < len2; j++){if(grid[i][j] == 1){done = false;return -1;}}}return count;}
}

####### 如果你把这题也看懂了，广度优先搜索的大门你以及迈进来一小小步了。上面的俩题都是力扣上面的简单题，如果你有自信，你可以根据笔者上面的解题思路，尝试一下这题中等题扫雷游戏，在这道题的题解区，有笔者的题解，如果有何疑问可以瞅瞅题解，它会给你答案的

希望各位在AC的道路上，越走越顺

这里给出前面提到的深度优先搜索解决最小深度的Code:

    public int dfs(TreeNode root){if(root == null){return Integer.MAX_VALUE;}if(root.left == null && root.right == null){return 1;}int leftCount = 0;int rightCount = 0;leftCount = bfs(root.left);rightCount = bfs(root.right);return (leftCount < rightCount ? leftCount : rightCount) + 1;}

具体思路在这里就不讲解啦，等到下次出深度优先搜索的时候再来说

笔者能力有限，如有错误，请见谅，一定虚心接受