C++实现邻接表存储图的广度优先遍历

好的，以下是 C++ 实现邻接表存储图的广度优先遍历的代码：

#include <iostream>
#include <queue>
#include <vector>
using namespace std;

const int MAXN = 100; // 最大顶点数
vector<int> adj[MAXN]; // 邻接表存储图
bool vis[MAXN]; // 标记数组

void BFS(int s) { // s 为起点
    queue<int> q;
    q.push(s);
    vis[s] = true;
    while (!q.empty()) {
        int u = q.front();
        cout << u << " ";
        q.pop();
        for (int i = 0; i < adj[u].size(); i++) {
            int v = adj[u][i];
            if (!vis[v]) {
                vis[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);
        adj[v].push_back(u); // 无向图
    }
    BFS(1); // 从顶点 1 开始遍历
    return 0;
}

代码解释：

- `MAXN`：定义最大顶点数；
- `adj`：定义邻接表，`adj[i]` 表示与顶点 `i` 相邻的顶点集合；
- `vis`：定义标记数组，`vis[i]` 表示顶点 `i` 是否已访问；
- `BFS` 函数：广度优先遍历函数；
- `queue`：STL 标准库中的队列，用于实现广度优先遍历；
- `n` 和 `m`：输入的顶点数和边数；
- `for` 循环：输入每条边；
- `BFS(1)`：从顶点 `1` 开始遍历。

注意：这是一个无向图的实现。如果是有向图，那么在输入边的时候只需要将 `adj[v].push_back(u);` 这行代码去掉即可。