广度优先搜索c++

以下是 C++ 语言实现的广度优先搜索算法的示例代码：

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

using namespace std;

const int MAXN = 100; // 最大节点数
vector<int> G[MAXN]; // 图的邻接表表示
bool vis[MAXN]; // 标记节点是否访问过

void bfs(int s) {
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        // 处理节点 u
        for (int i = 0; i < G[u].size(); ++i) {
            int v = G[u][i];
            if (!vis[v]) {
                q.push(v);
                vis[v] = true;
            }
        }
    }
}

int main() {
    // 构建图
    G[1].push_back(2);
    G[1].push_back(3);
    G[2].push_back(4);
    G[2].push_back(5);
    G[3].push_back(5);
    G[4].push_back(6);
    G[5].push_back(6);
    // 从节点 1 开始进行广度优先搜索
    bfs(1);
    return 0;
}

上述代码中，我们首先定义了一个邻接表数组 `G`，用于存储图的边信息。然后定义了一个标记数组 `vis`，用于标记每个节点是否被访问过。在 `bfs` 函数中，我们使用了 `queue` 容器来实现广度优先搜索，从起始节点 `s` 开始进行搜索。在搜索过程中，我们首先将起始节点 `s` 入队，并将其标记为已访问。接着，我们不断从队列中取出节点进行扩展，扩展过程中将未访问过的邻居节点入队，并将其标记为已访问。最终，所有与起始节点 `s` 连通的节点都会被访问一遍。