广度优先搜索bfs（广度优先搜索bfs全称）



        借用百度百科对BFS的解释

宽度优先搜索算法（又称广度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。其别名又叫BFS，属于一种盲目搜寻法，目的是系统地展开并检查图中的所有节点，以找寻结果。换句话说，它并不考虑结果的可能位置，彻底地搜索整张图，直到找到结果为止。

       BFS不同于DFS，借助的不是栈而是队列，BFS的思想是一层一层往下搜，但究其根本，其与DFS一样是一种暴搜法，会搜索整张图（或树），而不考虑结果可能会出现的位置去做专门的应对。

        基于其一层层搜的思想，我们可以推出以下基本的代码模型

      顾名思义，对于树型结构，层序遍历就是按层从上到下，每层按一定顺序对树的节点进行遍历，其基于的思想即为BFS。

代码如下：

        当数据量不会特别大时，可以考虑使用BFS搜寻最短路，因为搜寻过程为一层层搜寻，所以第一次碰到目标点时，一定为最短路。

原题链接 111. 二叉树的最小深度 - 力扣（LeetCode）

        求得树的最小深度，可以转化为找到离根节点最近的叶子节点，由于我们有第一次碰到目标点一定为最短路的结论，所以可以得知当第一次遇到一个结点为叶子结点时，其深度为最小深度。

        代码表示如下

原题链接：844. 走迷宫 - AcWing题库

题目模型为：在迷宫中从（1，1）移动至（n，m）求最短路 ，遇到1不能走。

本题只需注意在边界外封上一圈 “1墙”就可以开始搜寻了。

以上即是本篇对于BFS基础的全部分享了，如有问题欢迎提出指正。 

版权声明：

本文来自互联网用户投稿，该文观点仅代表作者本人，不代表本站立场。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。
如若内容造成侵权、违法违规、事实不符，请将相关资料发送至xkadmin@xkablog.com进行投诉反馈，一经查实，立即处理！

转载请注明出处，原文链接：https://www.xkablog.com/bcyy/25777.html