广度优先搜索（遍历）是一种在图的搜索遍历中较常见的算法。它的时间复杂度通常要比深度优先搜索（遍历）要低很多，尤其是最短路。这是因为深度优先的思想是走一条路要把它走到底再去考虑别的路，如果一开始走错了，后面会浪费很多时间在死胡同上，而且递归的方法本来就需要来一次回一次。而广度优先的思想则是让每一条路都向前进发一格，那么走错路不用付出太多代价，而且这样你第一次遇到终点就是答案，因为你每条路都是同层次。层次越少，答案越好。dfs那就惨了，要弄出所有的答案进行对比。它还无需考虑递归出所以函数的return的问题。它还不会那么容易爆栈。
bfs基本都是用队列实现的。因为它是先进先出的。先进去的结点永远都是先搜完的。
那队列是怎么操作的呢？别急，慢慢来。首先，我们要把起点push进队列，表示它即将搜索，并标记表示搜过的数组vis记下vis[起点]=1。然后，将起点的数据（坐标、步数、状态等）都保存在一个临时变量里，并将起点pop掉，因为它接下来搜完使命就结束了。接着，我们将所有起点（根据临时变量中的数据）能到达且合适的、没有搜过（!vis[该点]）的点都放进队列中，表示一会儿就要搜，再让vis[该点]=1，数据根据上个点按需求更改。之后每个点都像起点一样操作，不过是没有“首先”这一步骤的，因为在上个点搜索是它就设置好了。最后，如果队空，说明没有更多结点了，所以就退出。
对于下图，我给出了它的bfs和dfs搜索顺序：
（代码为c++语言）
定义图
讯享网
定义队列（需要加头文件<queue>）
讯享网
vis数组
定义函数
讯享网
初始化起点
中间部分
讯享网
1.走迷宫
题目要求
n*m的迷宫。S是起点，E是终点，#是墙壁，*是路。一段路需要1分钟行走。输出S到E的最短时间是几分钟。如果不能到达，输出-1。请使用bfs。0<n,m<=10^4
输入
输入n和m，之后n行每行m个字符。
输出
输出要求的数。
代码：
不过你也能看到，编程复杂度有点高。。。
2.图的最短路
题目要求
给出n个点m条边的无向图，告诉我从点1到其他所有点的最短路（换行隔开）。
保证每个点都是连通的。0<n,m<10^4
输入
首先输入n和m。然后m行输入两个数u,v，表示u和v相连。
输出
按照题意输出。
提示：
回想vector查看连接点的方法或查看我的这篇文章。
代码：
讯享网
运行结果：
OK，恭喜你完成所有题目！
bfs是一个运用场景广泛的算法，时间复杂度也还不错，非常实用。欢迎大家在评论区指点反馈我在文章撰写中的不足！
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/145691.html