C++ 算法学习——1.3 双向广度优先搜索

时间：2024-10-16 18:50:52

双向广度优先搜索算法步骤：

  1. 初始化：

    • 从起始节点开始，分别初始化两个队列 q_forward 和 q_backward。
    • 将起始节点分别放入这两个队列中。
    • 初始化两个集合 visited_forward 和 visited_backward 用于记录已访问的节点。

  2. 循环：

    • 在循环中，分别从 q_forward 和 q_backward 中取出一个节点进行扩展。
    • 对于 q_forward，从当前节点开始探索其相邻节点，并将未访问过的相邻节点加入到 q_forward 中。
    • 对于 q_backward，从当前节点开始探索其相邻节点，并将未访问过的相邻节点加入到 q_backward 中。
    • 在每次扩展节点时，检查两个队列中是否存在相同的节点，如果存在则找到了一条双向路径。
    • 如果找到双向路径，停止搜索并合并两个路径。

  3. 终止条件：

    • 当两个队列中存在相同的节点，或者两个队列中的节点都被完全探索过后，算法终止。

C++代码示例：

#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>

using namespace std;

// 双向广度优先搜索
bool bidirectional_bfs(vector<vector<int>>& graph, int start, int target) {
    queue<int> q_forward, q_backward;
    unordered_set<int> visited_forward, visited_backward;

    q_forward.push(start);
    q_backward.push(target);
    visited_forward.insert(start);
    visited_backward.insert(target);

    while (!q_forward.empty() && !q_backward.empty()) {
        // 扩展正向队列
        int curr_forward = q_forward.front();
        q_forward.pop();

        for (int neighbor : graph[curr_forward]) {
            if (!visited_forward.count(neighbor)) {
                visited_forward.insert(neighbor);
                q_forward.push(neighbor);
            }

            if (visited_backward.count(neighbor)) {
                cout << "Path found!";
                return true;
            }
        }

        // 扩展反向队列
        int curr_backward = q_backward.front();
        q_backward.pop();

        for (int neighbor : graph[curr_backward]) {
            if (!visited_backward.count(neighbor)) {
                visited_backward.insert(neighbor);
                q_backward.push(neighbor);
            }

            if (visited_forward.count(neighbor)) {
                cout << "Path found!";
                return true;
            }
        }
    }

    cout << "Path not found!";
    return false;
}

上为邻接表形式，接下来给出矩阵形式：

#include <iostream>
#include <queue>
#include <unordered_set>
#include <vector>
using namespace std;
int rows,cols;

void showcurboard(int** boa){
    for(int i=0;i<rows;i++)
    {
        for(int j=0;j<cols;j++)
        cout<<boa[i][j];
        cout<<endl;
    }
}

struct Coordinate {
    int x;
    int y;
    Coordinate(int _x, int _y) : x(_x), y(_y) {}
};
struct PairHash {
    template <class T1, class T2>
    std::size_t operator () (const std::pair<T1, T2> &pair) const {
        auto hash1 = std::hash<T1>{}(pair.first);
        auto hash2 = std::hash<T2>{}(pair.second);
        return hash1 ^ hash2;
    }
};
vector<pair<int, int>> directions = {{1, 0}, {-1, 0}, {0, 1}, {0, -1}};
bool bidirectional_bfs(int** matrix, int begina, int beginb, int enda, int endb) {
    queue<Coordinate> q_forward, q_backward;
    unordered_set<pair<int, int>, PairHash> visited_forward, visited_backward;

    q_forward.push(Coordinate(begina, beginb));
    q_backward.push(Coordinate(enda, endb));
    visited_forward.insert({begina, beginb});
    visited_backward.insert({enda, endb});

    while (!q_forward.empty() && !q_backward.empty()) {
        Coordinate curr_forward = q_forward.front();
        q_forward.pop();

        for (auto& dir : directions) {
            int new_x = curr_forward.x + dir.first;
            int new_y = curr_forward.y + dir.second;

            if (new_x >= 0 && new_x < rows && new_y >= 0 && new_y < cols && visited_forward.count({new_x, new_y}) == 0) {
                visited_forward.insert({new_x, new_y});

                if (visited_backward.count({new_x, new_y}) > 0) {
                    return true;
                }

                q_forward.push(Coordinate(new_x, new_y));
            }
        }

        Coordinate curr_backward = q_backward.front();
        q_backward.pop();

        for (auto& dir : directions) {
            int new_x = curr_backward.x + dir.first;
            int new_y = curr_backward.y + dir.second;

            if (new_x >= 0 && new_x < rows && new_y >= 0 && new_y < cols && visited_backward.count({new_x, new_y}) == 0) {
                visited_backward.insert({new_x, new_y});

                if (visited_forward.count({new_x, new_y}) > 0) {
                    return true;
                }

                q_backward.push(Coordinate(new_x, new_y));
            }
        }
    }
    return false;
}

int main()
{
    int a,b;cin>>rows>>cols>>a>>b;
    int** board=new int*[rows];
    for(int i=0;i<rows;i++)
    {
        board[i]=new int[cols];
        fill(board[i],board[i]+cols,0);
    }
    //showcurboard(board);
    return 0;
}

 

相关文章