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就表示队列的存储空间满了。
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/141711.html