如何使用C++中的广度优先搜索算法

使用C++中的广度优先搜索算法

广度优先搜索算法（BFS）是一种图搜索算法，它从图的起点开始，依次访问和探索各个节点，直到找到目标节点或者遍历完整个图。BFS使用队列来实现，首先将起点节点入队，然后将其相邻节点入队，依次进行下去，直到队列为空。

以下是一个使用C++实现广度优先搜索算法的示例代码：

#include 
#include 
#include 
using namespace std;

// 图的节点
struct Node {
    int id;
    bool visited;
    vector neighbors;
    Node(int _id) : id(_id), visited(false) {}
};

// 广度优先搜索算法
void BFS(Node* start) {
    // 使用队列保存要访问的节点
    queue q;
    // 标记起点已经被访问
    start->visited = true;
    q.push(start);

    while (!q.empty()) {
        Node* current = q.front();
        q.pop();
        cout << current->id << " ";

        // 遍历当前节点的相邻节点
        for (Node* neighbor : current->neighbors) {
            // 如果相邻节点未被访问，则标记为已访问并入队
            if (!neighbor->visited) {
                neighbor->visited = true;
                q.push(neighbor);
            }
        }
    }
}

int main() {
    // 创建图的节点
    Node* A = new Node(1);
    Node* B = new Node(2);
    Node* C = new Node(3);
    Node* D = new Node(4);
    Node* E = new Node(5);

    // 构建节点之间的连接关系
    A->neighbors.push_back(B);
    A->neighbors.push_back(C);
    B->neighbors.push_back(A);
    B->neighbors.push_back(D);
    C->neighbors.push_back(A);
    C->neighbors.push_back(D);
    D->neighbors.push_back(B);
    D->neighbors.push_back(C);
    D->neighbors.push_back(E);
    E->neighbors.push_back(D);

    // 从节点A开始进行广度优先搜索
    cout << "BFS traversal starting from node A: ";
    BFS(A);

    return 0;
}

以上代码中，我们首先定义了一个图的节点结构Node，其中包含节点的ID、是否访问过和相邻节点的指针列表。然后，我们实现了广度优先搜索算法BFS，使用队列来保存要访问的节点。在每次循环中，我们取出队列的首个节点，将其ID输出，并遍历其相邻节点，将未被访问过的节点加入队列中。最后，在main函数中创建了一个简单的图，并从节点A开始进行广度优先搜索。

Cursor

一个新的IDE，使用AI来帮助您重构、理解、调试和编写代码。

下载

立即学习“C++免费学习笔记（深入）”；

通过这个示例代码，我们可以理解和使用C++中的广度优先搜索算法，用于查找图中的连通节点、求解最短路径等问题，从而应用于各种实际场景。