小白式紧脏，尽量少说废话。如有问题，还望批评指教。

BFS（Breath First Search），又称广度优先遍历。
顾名思义，它是一种在优先在广度范围上遍历的一种方式，它用博大的胸怀一次包容”一层”节点。与之对应的就是DFS(Deep First Search)，深度优先遍历，一直深入到头后再返回。

1. BFS是如何工作的？

在学习数据结构课程的时候，初遇BFS是在图的遍历。但是BFS的应用场景不仅限于真正的图结构。更多时候我们可以遇到树的访问，二维矩阵图，HashMap邻接表等等场景。但无论什么场景，都要发现BFS的本质所在，就是 队列和访问标记集合。下面就单独来聊聊他们。
什么是队列？数据结构中说过，队列是一种FIFO（先进先出）的数据结构，类似于食堂排队买饭，先来的就要先买到饭。根据BFS的特性，我们要对一个结构进行广度优先的访问就必须要用到队列这个工具。

以你眼前的这课二叉树为例。
image.png
初始操作都是将根节点入队，这个根节点可以作为BFS的一个“源”，是BFS的开始。
进入主循环操作后，从队列中取出第一个节点0，将与之相邻的下一层（这里是0的孩子节点1和2）入队，此时队列中是1和2，接下来继续循环，然后取出第一个节点1，将与之相邻的下一层入队，此时队列中是2，4，继续循环下去。循环的终止条件是队列为空，因为从图中可以看到，叶子节点再没有与之相邻的下层元素了，就什么都不添加，如此反复队列终会为空。
那到这里就可以看出为什么BFS用的是队列而不是栈了，我们知道栈是一种后进先出的数据结构，假如说BFS用了栈，某个节点入栈之后又接着出栈访问他相邻的元素，达到的是一种深度优先的效果。

2. 如何用代码实现BFS

在Java中实现一个基础的BFS的模板很简单，借助于LinkedList实现队列效果。主要的4个步骤都写在注释里了。而代码中所说的也在上面的文字叙述中提到过。
模板1【适用于二叉树】

  1.  void bfs(TreeNode treeNode) {
  2.      LinkedList<TreeNode> queue = new LinkedList<>();
  3.      //1. 添加源
  4.      queue.offerLast(treeNode);
  5.      //2. 队列不空持续循环
  6.      while (!queue.isEmpty()) {
  7.          //3.队首出队
  8.          TreeNode node = queue.pollFirst();
  9.          System.out.println(node.val);
  10.          //4.添加与之相邻的节点
  11.          if (node.left != null) queue.offerLast(node.left);
  12.          if (node.right != null) queue.offerLast(node.right);
  13.      }
  14.  }

那掌握了这个模板我该怎么用呢？不知道你有没有注意到上面代码的3和4步骤中的打印语句，如果单纯的是遍历，的确打印语句就可以满足要求，但是如果是更复杂的计数？或者其他操作你该怎么办？举个简单的例子，如何计算一棵树有多少个节点。相信不用我说你也知道将打印语句替换为 count++。代码就是可以如此灵活的变通。
在掌握了上面的代码之后，我们可以小试牛刀。实现LeetCode 559. N叉树的最大深度 这个题。
image.png
要求求一棵N叉树的最大深度，也就是有多少层，这就要发挥我们BFS的作用了，因为BFS在树中又有另一个名字叫 “层序遍历”。那么我们先把模板Ctrl CV一下吧。

  1. public int maxDepth(Node root) {
  2.     LinkedList<Node> queue = new LinkedList<>();
  3.     //1. 添加源
  4.     queue.offerLast(root);
  5.     //2. 队列不空持续循环
  6.     while (!queue.isEmpty()) {
  7.         //3.队首出队
  8.         Node cur = queue.pollFirst();
  9.         //4.添加与之相邻的节点
  10.         List<Node> children = cur.children;
  11.         if (children == null) continue;
  12.         for (int i = 0; i < children.size(); i++) {
  13.             Node child = cur.children.get(i);
  14.             if(child != null)queue.offerLast(child);
  15.         }
  16.     }
  17.     return 0;
  18. }

上述代码和之前的代码几乎一样，只是因为这是一棵N叉树，所以我们第4步做了一个循环入队操作。那么现在在于我们怎么统计层数，在3，4之间count++似乎完不成这个任务。最能直觉想到的是如果我能记录每个节点所在的层数就好了，每次访问他的孩子节点的时候就层数加一，最终统计最大的层数就是答案。

  1. public int maxDepth(Node root) {
  2.     if(root == null)return 0;
  3.     int maxLevel = 1;
  4.     LinkedList<NodeWithLevel> queue = new LinkedList<>();
  5.     //1. 添加源
  6.     queue.offerLast(new NodeWithLevel(root, 1));
  7.     //2. 队列不空持续循环
  8.     while (!queue.isEmpty()) {
  9.         //3.队首出队
  10.         NodeWithLevel cur = queue.pollFirst();
  11.         //4.添加与之相邻的节点
  12.         List<Node> children = cur.node.children;
  13.         if (children == null) continue;
  14.         for (Node child : children) {
  15.             if (child != null) {
  16.                 queue.offerLast(new NodeWithLevel(child, cur.level + 1));
  17.                 maxLevel = Math.max(maxLevel, cur.level + 1);
  18.             }
  19.         }
  20.     }
  21.     return maxLevel;
  22. }
  24. class NodeWithLevel {
  25.     Node node;
  26.     int level;
  28.     public NodeWithLevel(Node node, int level) {
  29.         this.node = node;
  30.         this.level = level;
  31.     }
  32. }

上面的代码是一个正确的解答，其实也没什么特别之处，只是用一个NodeWithLevel结构记录了每个节点的所在层，并在level发生改变的时候统计最大值。
但这就是最佳答案了吗？有没有更简单的方法呢？答案当然是有。我们完全可以省略定义的结构改成如下样子。

  1. public int maxDepth(Node root) {
  2.     if (root == null) return 0;
  3.     int maxLevel = 0;
  4.     LinkedList<Node> queue = new LinkedList<>();
  5.     //1. 添加源
  6.     queue.offerLast(root);
  7.     //2. 队列不空持续循环
  8.     while (!queue.isEmpty()) {
  9.         //3.当前层全部出队
  10.         maxLevel++;
  11.         //3.1 需要单独计算长度
  12.         int size = queue.size();
  13.         for (int i = 0; i < size; i++) {
  14.             Node cur = queue.pollFirst();
  15.             //4.添加与之相邻的节点
  16.             List<Node> children = cur.children;
  17.             if (children == null) continue;
  18.             for (Node child : children) {
  19.                 if (child != null) {
  20.                     queue.offerLast(child);
  21.                 }
  22.             }
  23.         }
  24.     }
  25.     return maxLevel;
  26. }

可以看到第三步发生了变化。通过for循环将队列中现存的节点全部出队。这样会保证每次执行到while循环开始的时候都是准备处理下一层。在这个时机我们让层数计数自增以达到最终结果。

注意3.1注释地方，一定要缓存下队列长度，for循环中使用队列长度，否则队列长度一直在变，会影响for循环语句正常运行。

通过上面这个例子我们可以看出来，围绕着BFS模板，我们可以改它的打印语句部分，3部分和4部分以适应不同题目要求。

3. 这样就结束了吗？

如此，你便掌握了树的BFS操作。并能胜任大部分N叉树的BFS套题，那这样就是掌握了BFS了吗？并不是，因为上面给到的模板仅仅是针对于二叉树，或者灵活变通为兼容N叉树。
我们说初次遇见BFS的时候是在图中，那么接下来会遇到什么挑战呢？试想有这样一幅图。
image.png
这是一幅有环的图，假设我们选1为源点，复现模板1的操作步骤，1入队后出队，与之有直接指向关系的2入队，2出队，3入队。最后3出队，又遇到了1。如果此时我们再继续执行下去就会 “CPU不想跟你说话，并抛出了一个死循环警告⚠️” 了，那我们如何控制呢？最直观的想法，大不了我们就标志一下访问过不就好了。因此我们的访问标志集合诞生了。
下面是使用上面的多叉树的第一份代码来改进的。
模板2【适用于图或者二维矩阵结构】

  1. public void bfs(Node root) {
  2.     LinkedList<Node> queue = new LinkedList<>();
  3.     //访问标记集合
  4.     Set<Node> set = new HashSet<>();
  5.     //1. 添加源
  6.     queue.offerLast(root);
  7.     set.add(root);
  8.     //2. 队列不空持续循环
  9.     while (!queue.isEmpty()) {
  10.         //3.队首出队
  11.         Node cur = queue.pollFirst();
  12.         //4.添加与之相邻的节点
  13.         List<Node> children = cur.children;
  14.         if (children == null) continue;
  15.         for (int i = 0; i < children.size(); i++) {
  16.             Node child = cur.children.get(i);
  17.             //已访问的不会再添加
  18.             if (set.contains(child)) continue;
  19.             if (child != null) {
  20.                 queue.offerLast(child);
  21.                 //标志已访问
  22.                 set.add(child);
  23.             }
  24.         }
  25.     }
  26. }

上面的代码添加了Set集合来标志已访问的对象。对于已经访问过的对象，下次再遇到的时候就不会再加入队列了。
通常情况下，我们不需要掌握第一个模板，因为它并不是一个通用的板子，我自我认为不管是什么结构，都加入访问标志为好，这样不仅可以做一些计数功能，还能防止重复访问或者陷入死循环的情况，而在代码上面也不会有太多的消耗（除非对空间比较严格）

4. 使用模板做各种扩展

前面说到过，BFS其实可以用在各种场景，比如leetcode很“火爆”的海岛问题就是BFS的一个非常好的应用。695. 岛屿的最大面积 让你求一个二维矩阵（0代表海洋，1代表陆地）所表示的图中陆地的最大面积。求岛屿的最大面积，无非是把所有可能的岛屿的面积都比较一下，那么我们如何求一个岛屿有多大呢？用BFS就可以啊，于是有了如下代码。

  1. int bfs(int[][] nums, int sX, int sY) {
  2.     int ans = 0;
  3.     int xLen = nums.length;
  4.     int yLen = nums[0].length;
  5.     int[] x = new int[]{-1, 1, 0, 0};
  6.     int[] y = new int[]{0, 0, -1, 1};
  7.     //队列，必备。
  8.     LinkedList<Point> queue = new LinkedList<>();
  9.     //添加源，这里是用一个Point标记坐标，Point里包含了x，y坐标两个字段 
  10.     queue.offerLast(new Point(sX, sY));
  11.     //访问后，我们直接改为其他值做访问标记，这里就不需要Set那么麻烦了。
  12.     nums[sX][sY] = 2;
  13.     //队列不空就循环
  14.     while (!queue.isEmpty()) {
  15.         //取出队头结点
  16.         Point point = queue.pollFirst();
  17.         //统计面积
  18.         ans++;
  19.         //对其周围上下左右4个方向来判断是否合法，如果合法就入队，下面提到了几种不合法的情况
  20.         for (int i = 0; i < 4; i++) {
  21.             int curX = point.x + x[i];
  22.             int curY = point.y + y[i];
  23.             //如果产生的越界，就跳过本次
  24.             if (curX < 0 || curX >= xLen || curY < 0 || curY >= yLen) continue;
  25.             //如果已经访问过，就跳过本次，如果是海洋也跳过。
  26.             if (nums[curX][curY] == 2 || nums[curX][curY] == 0) continue;
  27.             //否则就入队
  28.             queue.offerLast(new Point(curX, curY));
  29.             //将此节点标志为已访问
  30.             nums[curX][curY] = 2;
  31.         }
  32.     }
  33.     return ans;
  34. }

可以看到上面的代码对于几个地方做了一点小技巧。

  • 访问数组的地方，我们不用Set了，而是直接操作了数组，因为数组天生访问快捷，且不需要再浪费额外的空间。对于本题破坏数组不会影响答案正确性，所以我们直接用一个自定的与众不同的数来标识访问。
  • for循环的地方我用了一个x，y数组来实现的4临界点访问，这个技巧也很常用，一方面是对于越界的处理更快捷了（数组环境中不是判断个null就可以过的，因为数组可以抛出访问越界异常），这个地方你可以仔细品味一下4临界的实现，同理还有8临界访问。

纵观全部代码，我们在开篇提到过的内容其实都有，只是写法更贴近实际场景。有了单个岛屿的面积，接下来求所有的岛屿面积进行比较
如果你也学会了灵活变通，那么恭喜你。你掌握了基本的广度优先遍历套路。

5. 总结与练习

上面给出的是基础的BFS框架，BFS可以应用于各种场景，同时也可以有多个源的版本。在后面还会有一篇文章专门聊聊多源BFS。那么为了更好的了解多源BFS，先做几个单源的题目吧。广度优先遍历合集 可以从easy开始练习。
image.png