借用百度百科对BFS的解释
宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。
BFS不同于DFS，借助的不是栈而是队列，BFS的思想是一层一层往下搜，但究其根本，其与DFS一样是一种暴搜法，会搜索整张图（或树），而不考虑结果可能会出现的位置去做专门的应对。
基于其一层层搜的思想，我们可以推出以下基本的代码模型
讯享网
顾名思义，对于树型结构，层序遍历就是按层从上到下，每层按一定顺序对树的节点进行遍历，其基于的思想即为BFS。
代码如下：
讯享网
当数据量不会特别大时，可以考虑使用BFS搜寻最短路，因为搜寻过程为一层层搜寻，所以第一次碰到目标点时，一定为最短路。
原题链接 111. 二叉树的最小深度 - 力扣（LeetCode）
求得树的最小深度，可以转化为找到离根节点最近的叶子节点，由于我们有第一次碰到目标点一定为最短路的结论，所以可以得知当第一次遇到一个结点为叶子结点时，其深度为最小深度。
代码表示如下
原题链接：844. 走迷宫 - AcWing题库
题目模型为：在迷宫中从（1，1）移动至（n，m）求最短路 ，遇到1不能走。
本题只需注意在边界外封上一圈 “1墙”就可以开始搜寻了。
讯享网
以上即是本篇对于BFS基础的全部分享了，如有问题欢迎提出指正。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/171686.html