双向广度优先搜索

什么是双向 BFS？
双向 BFS（Bidirectional Breadth-First Search）是一种图搜索算法，它从起点和终点同时开始搜索，以求得最短的路径。相比于普通的 BFS 算法，双向 BFS 算法可以减少搜索的节点数，从而提高搜索效率。
在双向 BFS 算法中，我们使用两个队列或集合分别记录从起点和终点出发的可达节点，并在每一轮中交替地从两个队列或集合中选择一个节点进行扩展。如果某个节点在两个方向上都被访问到了，那么说明在这两个节点之间存在一条路径。

双向 BFS 的优势
与普通的 BFS 算法相比，双向 BFS 算法具有以下优势：
搜索的节点数更少。由于双向 BFS 算法从两个方向同时开始搜索，因此它的搜索深度只需要普通 BFS 算法的一半，从而减少了搜索的节点数。
搜索的速度更快。由于双向 BFS 算法从起点和终点同时开始搜索，因此它的搜索速度更快。
能够避免无效搜索。由于双向 BFS 算法是从起点和终点同时开始搜索，因此它可以避免搜索那些无效的节点。

双向 BFS 的应用场景
双向 BFS 算法常用于求解最短路径问题，例如：

单词接龙问题
迷宫问题
网络延迟时间问题
火车换乘问题
双向 BFS 的实现步骤
双向 BFS 算法的实现步骤如下：

定义两个队列Qstart和 Qend，分别用于记录从起点和终点开始的可达节点。同时，定义两个集合visitstart和 visitend，用于记录每个节点是否被访问过。

将起点加入 Qstart和 visitstart中，将终点加入 Qend和 visitend中。从Qstart和Qend中分别取出一个节点，使用 BFS 的方法进行扩展，并记录每个节点的距离和前驱节点列表。如果某个节点在两个方向上都被访问到了，那么说明在这两个节点之间存在一条路径。
如果某一方向的队列为空，则结束搜索。否则，交替从两个队列中选择一个队列进行扩展。
如果在搜索过程中发现了重复节点，需要根据具体情况决定是否将其从队列中删除。
如果搜索结束时没有找到终点，则说明不存在从起点到终点的路径。

代码演示：

#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
using namespace std;

// 双向广度优先搜索的辅助函数
bool searchLevel(const vector<vector<int>>& graph, queue<int>& Q, unordered_set<int>& visitedCurrent, unordered_set<int>& visitedOpposite) {
    int levelSize = Q.size();
    for (int i = 0; i < levelSize; ++i) {
        int node = Q.front();
        Q.pop();

        for (const int& neighbor : graph[node]) {
            if (visitedOpposite.count(neighbor)) {
                return true;  // 找到交汇点
            }

            if (!visitedCurrent.count(neighbor)) {
                visitedCurrent.insert(neighbor);
                Q.push(neighbor);
            }
        }
    }
    return false;
}

// 双向广度优先搜索主函数
bool bidirectionalBFS(const vector<vector<int>>& graph, int start, int end) {
    if (start == end) return true;

    // 初始化队列和集合
    queue<int> Qstart, Qend;
    unordered_set<int> visitStart, visitEnd;

    Qstart.push(start);
    visitStart.insert(start);

    Qend.push(end);
    visitEnd.insert(end);

    while (!Qstart.empty() && !Qend.empty()) {
        // 从起点方向进行一层搜索
        if (searchLevel(graph, Qstart, visitStart, visitEnd)) {
            return true;  // 找到交汇点
        }

        // 从终点方向进行一层搜索
        if (searchLevel(graph, Qend, visitEnd, visitStart)) {
            return true;  // 找到交汇点
        }
    }
    return false;  // 未找到路径
}

int main() {
    int n = 6; // 图中节点的数量
    vector<vector<int>> graph(n); // 使用邻接表表示图

    // 添加边
    graph[0].push_back(1);
    graph[1].push_back(0);
    graph[0].push_back(2);
    graph[2].push_back(0);
    graph[1].push_back(3);
    graph[3].push_back(1);
    graph[2].push_back(4);
    graph[4].push_back(2);
    graph[3].push_back(5);
    graph[5].push_back(3);
    graph[4].push_back(5);
    graph[5].push_back(4);

    int start = 0;
    int end = 5;
    if (bidirectionalBFS(graph, start, end)) {
        cout << "找到路径！" << endl;
    } else {
        cout << "未找到路径。" << endl;
    }

    return 0;
}

使用 vector<vector<int>> 作为图的表示：图的邻接表直接使用一个 vector 来表示，每个节点的邻接节点存储在一个 vector<int> 中。

bidirectionalBFS 函数：双向广度优先搜索的主要函数。它初始化两个队列（Qstart 和 Qend）和两个集合（visitStart 和 visitEnd），并通过调用 searchLevel 函数来扩展每一层。

searchLevel 函数：用于扩展当前层的所有节点，并检查是否遇到了从对方向搜索到的节点。

主函数 main：设置图的结构和起点、终点，然后调用 bidirectionalBFS 来查找从起点到终点的路径。

Previous Lesson

Back to Lesson

Next Topic

数据结构与算法

双向广度优先搜索