详解C++图搜索算法之双端队列广搜

什么是双端队列广搜

双端队列广搜（Bidirectional Breadth-First Search）是一种图搜索算法，可用于无向图中两点之间的最短路径问题。与传统的广度优先搜索（BFS）相比，双端队列广搜同时从起点和终点出发，通过两端的搜索相遇来实现更快的搜索和更高的效率。

双端队列广搜算法步骤

1. 创建两个队列：起点队列和终点队列，分别存放起点和终点。
2. 分别从起点队列和终点队列中出队一个元素，对它们进行扩展。
3. 判断两端是否相遇，如果相遇则搜索结束，输出最短路径。否则，继续往两端扩展。
4. 在扩展时，如果两端的某一个节点已经在另一个队列中出现过了，说明搜索到了中间节点，则搜索结束，输出最短路径。

双端队列广搜示例

第一个示例

假设我们要找出无向图中节点1到节点8的最短路径，其中图中节点的连线关系如下：

1--2--3--4
|     |  |
5--6--7--8

则双端队列广搜的过程如下：

1. 节点1和节点8分别进入起点队列和终点队列。
2. 从起点队列中出队节点1，从终点队列中出队节点8。
3. 对节点1进行扩展，得到节点2和节点5。对节点8进行扩展，得到节点4和节点7。
4. 判断节点2和节点8是否相遇，没有相遇。判断节点4和节点5是否相遇，没有相遇。
5. 从节点2和节点4继续扩展，得到节点3和节点6。从节点5和节点7继续扩展，得到节点6和节点7。
6. 判断节点3和节点8是否相遇，没有相遇。判断节点6和节点5是否相遇，相遇了。搜索结束，输出最短路径为1-2-6-5-8。

第二个示例

假设我们要找出无向图中节点A到节点G的最短路径，其中图中节点的连线关系如下：

A--B--C
|  |  |
D--E--F--G

则双端队列广搜的过程如下：

1. 节点A和节点G分别进入起点队列和终点队列。
2. 从起点队列中出队节点A，从终点队列中出队节点G。
3. 对节点A进行扩展，得到节点B和节点D。对节点G进行扩展，得到节点F。
4. 判断节点B和节点G是否相遇，没有相遇。判断节点D和节点F是否相遇，没有相遇。
5. 从节点B和节点F继续扩展，得到节点C和节点E。
6. 判断节点C和节点G是否相遇，没有相遇。判断节点E和节点D是否相遇，没有相遇。
7. 从节点C和节点E继续扩展，得到节点F和节点D。
8. 判断节点F和节点D是否相遇，相遇了。搜索结束，输出最短路径为A-D-F-G。

参考资料

• 双向BFS（Bidirectional Breadth First Search）算法详解
• 双向广度优先搜索