广度优先搜索序列（广度优先搜索 队列）



1.1 队列

队列是线性表的一种，它是一种以“先进先出”原则（FIFO）的数据结构。它的规则是：在存储元素时，数据元素只能从表的一端进入队列，另一端出队列。如下图所示。

队列的实现方式：顺序存储和链式存储。

1.2 广度优先搜索

广度优先搜索（Breadth First Search BFS）是最简便的图的搜索算法之一。Dijkstra单源最短路径算法和Prim最小生成树算法都采用和BFS类似的思想。

BFS思想：像树的遍历当中的层序遍历，一层一层的搜索，搜索完一层后再搜下一层，直到最后得到想要的结果。

BFS适用于统计路径的条数，比如说走迷宫的问题。

通过广度优先搜索的规则可以看出，它可以和队列结合进行代码的编写。

BFS就是从图中的某个顶点出发，寻找紧邻的、尚未访问的顶点，找到多少就访问多少，然后分别从找到的这些顶点出发，继续寻找紧邻的、尚未访问的顶点。

BFS的一般步骤：

1. 从某一个顶点V0开始访问，并把顶点V0放入队列中。

2. 访问所有与顶点V0相邻接的顶点v1,v2,.....,Vt。

3. 重复依次访问与顶点v1,v2,.....,Vt相邻接未访问过的顶点。

4. 循此以往，直到所有的顶点都被访问过为止。

代码结构：

代码分析：

通过分析图可以看出代码巧妙运用predecessor成员指针。广度优先的一个特点就是可以找到从起点到终点的最短路径。而深度优先搜索不一定是最短路径。

由于广度优先搜索是一层一层的依次往下进行搜索，直到所有的顶点都被访问完截止。而最短路径一定是最先访问到最后终点的，所以打印出来的路线是最短的。

在之前讲过的用DFS解迷宫问题的栈操作和BFS解迷宫问题的队列操作可以发现，栈操作的top指针在入栈的时候进行增大，在出栈的时候减少，因此可以退出栈空间是可以重复利用的。

而队列操作中的head、tail指针都在一直增大，虽然前面的元素已经出队，但是所占的存储空间却不能重复利用。

上述的队列的出队元素仍然有用，可以保存走过的路径和每个店的前驱，但是大多数不是这样使用队列的，一般情况下出队的元素不再有保存价值，这些元素的存储空间应该回收利用，因此把队列改造成环形队列（Circular Queue）。

环形队列原理：

把queue数组想象成一个圈，head和tail指针仍然是一直增大，当指到数组末尾时就自动回到数组的开头。

从head到tail之间是队列的有效元素。

从tail到head之间是空的存储位置。

如果head追上tail就表明队列空了。

如果tail追上head就表示队列的存储空间满了。

版权声明：

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

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