最近刷题，凑巧刷到一些关于BFS的题，所以顺便总结一下BFS的解题方法。该博客面向新手小白，从入门到熟练BFS。如有不当的地方，也请真正精通BFS的大佬指正！
具体的内容会分为三个板块，以二叉树的层序遍历为引子，介绍BFS的原理，最后是多源BFS问题。具体的算法题会先描述解题思路，然后提供我的参考代码。
二叉树的层序遍历与常规三件套，前、中、后序遍历有所不同，个人认为层序遍历理解起来更直观。其核心思想为“老带新”，使用一个队列（先进先出）达成此目的。
- 如动图所示，我们从根节点开始遍历，首先初始化队列，将节点“1”入队列。
- 当节点“1”出队列的时候，对节点进行操作，同时让节点“1”的左右孩子，节点“2”，“3”入队列。【老节点将新节点带入队列】
- 反复循环入队列，出队列操作。如果某个节点的左节点（右节点）为空，就不进行入队列操作。
- 直到队列为空的时候，我们就对一棵二叉树完成了遍历。
【多叉树的层序遍历原理相同】
如果在遍历的时候需要考虑数据来自于哪一层，上述代码就失效了，因为队列中可能同时存在来自两层的节点，这时可以加入一个用以计数，就能解决问题。
102. 二叉树的层序遍历 - 力扣（LeetCode）
题目要求很简单，层序遍历二叉树，最终以二维数组的形式进行输出。思路便是上文提到的，在开始出队列操作前，使用一个记录队列中的节点数量（即属于同样深度的节点的数量），保证一个数组内的数都来自同一层。
当然，你也可以尝试再使用一个队列，在节点入队列的时候记录它来自哪一层，也可以达到相同目的。如果感兴趣，可以自己尝试实现以下。不过这样做的话，空间复杂度就是O(N)。
真正的BFS算法更多是运用于图的一种搜索策略，但是其实际思想仍然是上文介绍的“老带新”，只不过因为图本身的结构特性，我们在还需要一个布尔数组记录某个节点的状态（是否被搜素过），以避免重复地搜索。做两道题，你就能明白是怎么回事了:)
1306. 跳跃游戏 III - 力扣（LeetCode）
该题是对BFS算法的基础运用，分析题目后你会发现，它实际上和二叉树的结构很相似：要么向左跳跃（左孩子），要么向右跳跃（右孩子），或者无法跳跃（孩子为空，nullptr）。所以直接采用层序遍历的策略进行遍历，但是可能会出现跳到已经跳过的格子上，所以加一个与原数组相同大小的布尔数组以记录格子状态。
我的参考代码如下：
总结一下，BFS的基本套路：
- 初始化：创建一个队列来存储待访问的节点，并将起始节点加入队列。
- 记录状态：创建一个相同大小的布尔数组记录节点的状态；一个计数器，记录同层的节点数量。
- 访问节点：出队列操作，对节点进行操作。
- 入队列：判断节点邻居的状态，将它们入队列，并更改状态。
- 重复上述操作，直到所有节点已经被遍历。
多源BFS本质上并没有比BFS难，只是要同时处理多个格子的状态，处理好不同源之间的邻居关系，不能重复入队列或漏入队列即可。
1162. 地图分析 - 力扣（LeetCode）
我们在BFS中遍历的层数就是该题所求的曼哈顿距离，稍微改变BFS的一些细节就能解决这道题。
如图解所示，初始化队列的时候，将四角的陆地都入队列；第一轮遍历，遍历四个浅色格子；第二轮遍历，遍历到中间的深蓝色格子。总共遍历了两层格子，所以最终的答案就是2。
我的参考代码如下：
你可以用下面这道题检验一下自己，看有没有真的学会BFS！
994. 腐烂的橘子 - 力扣（LeetCode）
感谢你能看到这里，谢谢！
到此这篇广度优先搜索树（广度优先搜索序列怎么做）的文章就介绍到这了,更多相关内容请继续浏览下面的相关推荐文章，希望大家都能在编程的领域有一番成就！版权声明：
本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！
转载请注明出处，原文链接：https://www.xkablog.com/bcyy/72879.html