广度优先搜索怎么遍历（广度优先搜索遍历序列）



        广度优先搜索（遍历）是一种在图的搜索遍历中较常见的算法。它的时间复杂度通常要比深度优先搜索（遍历）要低很多，尤其是最短路。这是因为深度优先的思想是走一条路要把它走到底再去考虑别的路，如果一开始走错了，后面会浪费很多时间在死胡同上，而且递归的方法本来就需要来一次回一次。而广度优先的思想则是让每一条路都向前进发一格，那么走错路不用付出太多代价，而且这样你第一次遇到终点就是答案，因为你每条路都是同层次。层次越少，答案越好。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是一个运用场景广泛的算法，时间复杂度也还不错，非常实用。欢迎大家在评论区指点反馈我在文章撰写中的不足！

版权声明：

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

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