c++中如何检测图中环_c++图环检测方法

答案：无向图用并查集检测环，有向图可用DFS状态标记或拓扑排序；并查集适合无向图高效判环，DFS通过访问状态判断有向图环，Kahn算法在拓扑排序中检测环。

在C++中检测图中的环，常用方法取决于图的类型：有向图和无向图有不同的处理策略。下面介绍几种主流且实用的图环检测方法。

1. 无向图中的环检测（使用并查集）

对于无向图，可以使用并查集（Union-Find）来检测是否存在环。基本思路是：遍历每条边，如果边的两个顶点已经属于同一个集合，说明加入这条边会形成环。

#include <iostream>
#include <vector>
using namespace std;
<p>struct Edge {
int u, v;
};</p><p>class UnionFind {
public:
vector<int> parent;
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
}</p><pre class="brush:php;toolbar:false;">int find(int x) {
    if (parent[x] != x)
        parent[x] = find(parent[x]);
    return parent[x];
}

bool unite(int x, int y) {
    int rx = find(x), ry = find(y);
    if (rx == ry) return false;
    parent[rx] = ry;
    return true;
}

};

立即学习“C++免费学习笔记（深入）”；

Dora

创建令人惊叹的3D动画网站，无需编写一行代码。

下载

bool hasCycleUndirected(vector& edges, int n) { UnionFind uf(n); for (auto& e : edges) { if (!uf.unite(e.u, e.v)) return true; // 发现环 } return false; }

2. 有向图中的环检测（使用DFS）

对于有向图，常用深度优先搜索（DFS）配合三种节点状态：未访问、正在访问（递归栈中）、已访问。如果在DFS过程中遇到一个“正在访问”的节点，说明存在环。

#include <vector>
using namespace std;
<p>bool dfs(int u, vector<vector<int>>& graph, 
vector<int>& visited) {
if (visited[u] == 1) return true;  // 正在访问，发现环
if (visited[u] == 2) return false; // 已访问过，无环</p><pre class="brush:php;toolbar:false;">visited[u] = 1; // 标记为正在访问
for (int v : graph[u]) {
    if (dfs(v, graph, visited)) 
        return true;
}
visited[u] = 2; // 标记为已访问
return false;

}

bool hasCycleDirected(int n, vector>& graph) { vector visited(n, 0); // 0:未访问, 1:访问中, 2:已完成 for (int i = 0; i

3. 使用拓扑排序（仅适用于有向图）

有向无环图（DAG）可以进行拓扑排序。如果拓扑排序的结果包含所有节点，则无环；否则存在环。常用Kahn算法实现。

- 统计每个节点的入度。 - 将入度为0的节点加入队列。 - 不断取出节点，减少其邻居的入度，若某邻居入度为0则加入队列。 - 最终如果排序节点数少于总节点数，则存在环。

总结与选择建议

根据不同场景选择合适方法：

• 无向图：推荐使用并查集，简洁高效。
• 有向图：DFS状态标记法最直观，适合小图或需要快速实现的场景。
• 有向图+拓扑需求：用Kahn算法，在排序同时检测环。

基本上就这些常见做法，根据图的结构和数据规模灵活选用即可。