C++ 广度优先遍历 环路

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();
        cout << 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() {
    int n, m, s;
    cin >> n >> m >> s; // 输入顶点数、边数和起点
    for (int i = 0; i < m; i++) {
        int u, v;
        cin >> u >> v; // 输入一条边的两个端点
        G[u].push_back(v);
        G[v].push_back(u); // 无向图需要加上这一行
    }
    bfs(s); // 从起点s开始遍历
    return 0;
}