如何修改BFS环检测代码，输出无向无权图中构成环的所有顶点

核心修改思路 #

• 你现有代码中已经通过parent数组记录了BFS遍历过程中每个节点的父节点，当触发环检测条件visited[v] && parent[u] != v时，说明找到一条非父节点的回边u-v，这条边和BFS树上u到v的路径刚好构成完整的环。
• 此时不需要直接返回true，先通过parent数组分别回溯u和v的路径，提取出构成环的所有顶点存入列表即可。

修改后的完整代码 #

#include <bits/stdc++.h>
using namespace std;
 
void addEdge(vector<int> adj[], int u, int v)
{
    adj[u].push_back(v);
    adj[v].push_back(u);
}

// 新增cycle参数，用于返回检测到的环顶点
bool isCyclicConntected(vector<int> adj[], int s,
                        int V, vector<bool>& visited, vector<int>& cycle)
{
    vector<int> parent(V, -1);
    queue<int> q;
    visited[s] = true;
    q.push(s);
 
    while (!q.empty()) {
        int u = q.front();
        q.pop();
 
        for (auto v : adj[u]) {
            if (!visited[v]) {
                visited[v] = true;
                q.push(v);
                parent[v] = u;
            }
            // 检测到环存在
            else if (parent[u] != v) {
                // ------------ 新增：提取环顶点 ------------
                unordered_set<int> path_u;
                vector<int> temp_u;
                int cur = u;
                // 回溯u的路径，存入临时列表并标记
                while (cur != -1) {
                    temp_u.push_back(cur);
                    path_u.insert(cur);
                    cur = parent[cur];
                }
                // 回溯v的路径，直到找到和u路径的公共节点
                cur = v;
                vector<int> temp_v;
                while (path_u.find(cur) == path_u.end()) {
                    temp_v.push_back(cur);
                    cur = parent[cur];
                }
                // 拼接环：公共节点到u的路径 + v到公共节点的路径 + 公共节点（闭合环）
                int common = cur;
                for (int node : temp_u) {
                    cycle.push_back(node);
                    if (node == common) break;
                }
                reverse(temp_v.begin(), temp_v.end());
                for (int node : temp_v) {
                    cycle.push_back(node);
                }
                cycle.push_back(common);
                // ------------ 提取结束 ------------
                return true;
            }
        }
    }
    return false;
}

// 新增cycle参数
bool isCyclicDisconntected(vector<int> adj[], int V, vector<int>& cycle)
{
    vector<bool> visited(V, false);
    for (int i = 0; i < V; i++) {
        if (!visited[i] && isCyclicConntected(adj, i, V, visited, cycle))
            return true;
    }
    return false;
}
 
int main()
{
    int V = 4;
    vector<int> adj[V];
    addEdge(adj, 0, 1);
    addEdge(adj, 1, 2);
    addEdge(adj, 2, 0);
    addEdge(adj, 2, 3);
    
    vector<int> cycle;
    if (isCyclicDisconntected(adj, V, cycle)) {
        cout << "存在环，环的顶点为：" << endl;
        for (int i = 0; i < cycle.size(); i++) {
            if (i > 0) cout << " -> ";
            cout << cycle[i];
        }
        cout << endl;
    }
    else
        cout << "不存在环" << endl;
 
    return 0;
}

运行结果说明 #

针对你给出的测试用例，代码运行后会输出类似如下结果：

存在环，环的顶点为：
2 -> 1 -> 0 -> 2

输出的环顺序可能根据遍历顺序有差异，但所有构成环的顶点都会完整列出。

内容的提问来源于stack exchange，提问作者Eikichi Onizuka