图的广度优先搜索 C++代码

以下是一个基本的图的广度优先搜索的C++代码示例：

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

using namespace std;

const int MAXN = 100; // 图中最大节点数
vector<int> adj[MAXN]; // 图的邻接表表示
bool visited[MAXN]; // 记录节点是否被访问过

void bfs(int s) {
    queue<int> q; // 存储待访问的节点
    visited[s] = true;
    q.push(s);
    while (!q.empty()) {
        int u = q.front();
        q.pop();
        cout << u << " "; // 访问节点 u
        for (int v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
            }
        }
    }
}

int main() {
    int N, M; // N: 节点数，M: 边数
    cin >> N >> M;
    for (int i = 0; i < M; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v); // 添加一条 u->v 的有向边
    }
    bfs(0); // 从节点 0 开始进行 BFS
    return 0;
}

在这个示例中，我们使用邻接表表示图，并使用 STL 中的队列（queue）来存储待访问的节点。我们从起始节点开始进行 BFS，依次访问其相邻节点，并将尚未被访问的节点加入队列中。当队列为空时，搜索结束。

需要注意的是，在每次访问节点时，需要将其标记为已访问（visited）以避免重复访问。同时，我们也可以在 BFS 中记录每个节点的深度（即到起始节点的距离），以便进行一些更复杂的操作。