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

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

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

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

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

#include 
#include 
using namespace std;
struct Edge {
int u, v;
};
class UnionFind {
public:
vector parent;
UnionFind(int n) {
parent.resize(n);
for (int i = 0; i < n; i++) parent[i] = i;
}
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;
}

};
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过程中遇到一个“正在访问”的节点，说明存在环。

							

								
								

									百度智能云·曦灵
									
百度旗下的AI数字人平台
								
								下载 
							
						
立即学习“C++免费学习笔记（深入）”；
示例代码：
#include 
using namespace std;
bool dfs(int u, vector>& graph, 
vector& visited) {
if (visited[u] == 1) return true;  // 正在访问，发现环
if (visited[u] == 2) return 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算法，在排序同时检测环。

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