c++中如何检测图中环_c++图环检测方法-C++-PHP中文网

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

尼克

发布： 2025-11-11 21:09:02

原创

415人浏览过

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

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

在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;"><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;
}

登录后复制

};

bool hasCycleUndirected(vector<Edge>& 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过程中遇到一个“正在访问”的节点，说明存在环。

AGI-Eval评测社区

AI大模型评测社区

查看详情

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

示例代码：

#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;"><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<vector<int>>& graph) { vector<int> visited(n, 0); // 0:未访问, 1:访问中, 2:已完成 for (int i = 0; i < n; i++) { if (!visited[i] && dfs(i, graph, visited)) return true; } return false; }