用c++实现图的广度优先遍历

广度优先遍历（BFS）是一种基于队列实现的算法，用于遍历图中的所有节点。以下是使用C++实现广度优先遍历的示例代码：

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

using namespace std;

const int MAXN = 100; // 图中节点的最大数量

vector<int> adj[MAXN]; // 邻接表表示图
bool visited[MAXN]; // 标记某个节点是否已被访问

void bfs(int start) {
    queue<int> q;
    q.push(start);
    visited[start] = true;

    while (!q.empty()) {
        int cur = q.front();
        q.pop();
        cout << cur << " ";

        // 遍历当前节点的所有邻居
        for (int i = 0; i < adj[cur].size(); i++) {
            int next = adj[cur][i];
            if (!visited[next]) {
                visited[next] = true;
                q.push(next);
            }
        }
    }
}

int main() {
    int n, m;
    cin >> n >> m; // 输入节点数量和边数量

    // 输入边的信息（无向图）
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v;
        adj[u].push_back(v);
        adj[v].push_back(u);
    }

    // 从节点0开始遍历
    bfs(0);

    return 0;
}

在该代码中，我们使用了一个 `visited` 数组来标记某个节点是否已被访问，使用邻接表来表示图。在 `bfs` 函数中，我们首先将起始节点 `start` 加入队列 `q` 中，并将其标记为已访问。随后，我们不断从队列中取出节点并输出其编号，然后遍历该节点的所有邻居节点，将未被访问的邻居节点加入队列中，直到队列为空为止。由于广度优先遍历算法的时间复杂度为 $O(n+m)$（其中 $n$ 为节点数量，$m$ 为边数量），因此该算法可用于处理大规模的图。