广度优先搜索是什么类型（广度优先搜索序列怎么做）



【算法设计】用C++类和队列实现图搜索的广度优先遍历算法

C/C++ 之 广度优先搜索

算法讲解之广度优先搜索

本系列为C++算法学习系列，会介绍 算法概念与描述，入门算法，基础算法，数值处理算法，排序算法，搜索算法，图论算法， 动态规划等相关内容。本文为搜索算法部分。

广度优先搜索（Breadth-First Search），又称作宽度优先搜索。BFS是一种完备策略，即只要问题有解，它就一定可以找到解。并且，广度优先搜索找到的解，还一定是路径最短的解。但是它盲目性较大，尤其是当目标节点距初始节点较远时，将产生许多无用的节点，因此其搜索效率较低。一般只有需求最优解的时候会用BFS。

广度优先搜索算法（又称宽度优先搜索）是最简便的图的搜索算法之一，这一算法也是很多重要的图的算法的原型。Dijkstra单源最短路径算法和Prim最小生成树算法都采用了和宽度优先搜索类似的思想。

广度优先算法的核心思想是：从初始节点开始，应用算符生成第一层节点，检查目标节点是否在这些后继节点中，若没有，再用产生式规则将所有第一层的节点逐一扩展，得到第二层节点，并逐一检查第二层节点中是否包含目标节点。若没有，再用算符逐一扩展第二层的所有节点……，如此依次扩展，检查下去，直到发现目标节点为止。即

⒈从图中的某一顶点V0开始，先访问V0；
⒉访问所有与V0相邻接的顶点V1，V2，…，Vt；
⒊依次访问与V1，V2，…，Vt相邻接的所有未曾访问过的顶点；
⒋循此以往，直至所有的顶点都被访问过为止。
这种搜索的次序体现沿层次向横向扩展的趋势，所以称之为广度优先搜索。

迷宫问题

问题

现在有一个4*4的迷宫，李雷在迷宫的左上角，迷宫出口在右下角，李雷体力有限，他希望尽快走出迷宫，请你告诉李雷最少需要走多少步(每个格子不能重复走动)。

我们可以按照这样的思路去找:
1.从起点出发，检查第1步可以到达的所有点，判断是否为终点。
2.依次从第1步到达的点出发，检查判断第2步可以到达的点是否为终点。
3.依次从第2步到达的点出发，检查判断第3步可以到达的点是否为终点。
4.依次从第3步到达的点出发，检查判断第4步可以到达的点是否为终点。
5.依次从第4步到达的点出发，检查判断第5步可以到达的点是否为终点。
6.找到终点，程序结束，步数为5。

迷宫的存储

迷宫的移动

搜索方式

1.我们需要使用队列(que)来实现,用一个结构体表示每次找到的点的坐标信息以及步数(x,y,cnt)。
2将起点入队。
3.取出队首元素，队首后移(head++) ,将队首元素上下左右的四个点依次入队(步数cnt要+1)，同时判断是否到达终点，若到达终点则终止程序。
4.重复步骤3，直到找到终点或者队列为空(即head>tail)

代码实现

图的广度优先遍历

题目描述

使用广度优先遍历算法输出访问结点的顺序，结果为0、1、2、4、5、8、9、3、6、7、10

用邻接矩阵表示图

按照案例给出的图，我简化成了这个邻接矩阵，画法就是，两个结点之间相连设置为T，不相连设置为F，规定结点自身与自身不相连，当然对T和F要有声明，例如 const bool T =true,F=false;这样T就代表通路，F就代表断路了

在深度优先搜索算法中，是深度越大的结点越先得到扩展。如果在搜索中把算法改为按结点的层次进行搜索，本层的结点没有搜索处理完时，不能对下层结点进行处理，即深度越小的结点越先得到扩展，也就是说先产生的结点先得以扩展处理，这种搜索算法称为广度优先搜索法。

版权声明：

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

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