在图论中，环（英语：cycle）是一条只有第一个和最后一个顶点重复的非空路径。
在有向图中，一个结点经过两种路线到达另一个结点，未必形成环。
使用拓扑排序可以判断一个无向图中是否存在环，具体步骤如下：
求出图中所有结点的度。将所有度 <= 1 的结点入队。（独立结点的度为 0）当队列不空时，弹出队首元素，把与队首元素相邻节点的度减一。如果相邻节点的度变为一，则将相邻结点入队。循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过，无环；反之，则有环。使用拓扑排序判断无向图和有向图中是否存在环的区别在于：
在判断无向图中是否存在环时，是将所有度 <= 1 的结点入队；在判断有向图中是否存在环时，是将所有入度 = 0 的结点入队。（感谢 wangweijun@shen 指正！！！）使用 DFS 可以判断一个无向图和有向中是否存在环。深度优先遍历图，如果在遍历的过程中，发现某个结点有一条边指向已访问过的结点，并且这个已访问过的结点不是上一步访问的结点，则表示存在环。
我们不能仅仅使用一个 bool 数组来表示结点是否访问过。规定每个结点都拥有三种状态，白、灰、黑。开始时所有结点都是白色，当访问过某个结点后，该结点变为灰色，当该结点的所有邻接点都访问完，该节点变为黑色。
那么我们的算法可以表示为：如果在遍历的过程中，发现某个结点有一条边指向灰色节点，并且这个灰色结点不是上一步访问的结点，那么存在环。
#include <iostream> #include <queue> #include <vector> using namespace std; vector<vector<int>> g; vector<int> color; int last; bool hasCycle; bool topo_sort() { int n = g.size(); vector<int> degree(n, 0); queue<int> q; for (int i = 0; i < n; i++) { degree[i] = g[i].size(); if (degree[i] <= 1) { q.push(i); } } int cnt = 0; while (!q.empty()) { cnt++; int root = q.front(); q.pop(); for (auto child : g[root]) { degree[child]--; if (degree[child] == 1) { q.push(child); } } } return (cnt != n); } void dfs(int root) { color[root] = 1; for (auto child : g[root]) { if (color[child] == 1 && child != last) { hasCycle = true; break; } else if (color[child] == 0) { last = root; dfs(child); } } color[root] = 2; } int main() { int n = 4; g = vector<vector<int>>(n, vector<int>()); g[0].push_back(1); g[1].push_back(0); g[1].push_back(2); g[2].push_back(1); g[2].push_back(3); g[3].push_back(2); cout << topo_sort() << endl; //0，无环 color = vector<int>(n, 0); last = -1; hasCycle = false; dfs(0); cout << hasCycle << endl; //0，无环 g[0].push_back(3); g[3].push_back(0); cout << topo_sort() << endl; //1，有环 color = vector<int>(n, 0); last = -1; hasCycle = false; dfs(0); cout << hasCycle << endl; //1，有环 return 0; }我们可以使用并查集来判断一个图中是否存在环：
对于无向图来说，在遍历边（u-v）时，如果结点 u 和结点 v 的“父亲”相同，那么结点 u 和结点 v 在同一个环中。
对于有向图来说，在遍历边（u->v）时，如果结点 u 的“父亲”是结点 v，那么结点 u 和结点 v 在同一个环中。
#include <algorithm> #include <iostream> #include <vector> using namespace std; vector<pair<int, int>> g; vector<int> father; int findFather(int x) { int a = x; while (x != father[x]) { x = father[x]; } while (a != father[a]) { int z = a; a = father[a]; father[z] = x; } return x; } void Union(int a, int b) { int fa = findFather(a); int fb = findFather(b); father[a] = father[b] = min(fa, fb); } bool isCyclicUnirectedGraph() { for (int i = 0; i < g.size(); i++) { int u = g[i].first; int v = g[i].second; if (father[u] == father[v]) { return true; } Union(u, v); } return false; } bool isCyclicDirectedGraph() { for (int i = 0; i < g.size(); i++) { int u = g[i].first; int v = g[i].second; if (father[u] == v) { return true; } father[v] = findFather(u); } return false; } int main() { // Undirected acyclic graph // 0 // / \ // 1 2 g.push_back(make_pair(0, 1)); g.push_back(make_pair(0, 2)); for (int i = 0; i < 3; i++) { father.push_back(i); } cout << isCyclicUnirectedGraph() << endl; //0，无环 // Undirected cyclic graph // 0 // / \ // 1———2 g.push_back(make_pair(1, 2)); vector<int>().swap(father); for (int i = 0; i < 3; i++) { father.push_back(i); } cout << isCyclicUnirectedGraph() << endl; //1，有环 // Directed acyclic graph // 0 // / \ // v v // 1——>2 vector<pair<int, int>>().swap(g); g.push_back(make_pair(0, 1)); g.push_back(make_pair(1, 2)); g.push_back(make_pair(0, 2)); vector<int>().swap(father); for (int i = 0; i < 3; i++) { father.push_back(i); } cout << isCyclicDirectedGraph() << endl; //0，无环 // Directed cyclic graph // 0 // / ^ // v \ // 1——>2 g.pop_back(); g.push_back(make_pair(2, 0)); vector<int>().swap(father); for (int i = 0; i < 3; i++) { father.push_back(i); } cout << isCyclicDirectedGraph() << endl; //1，有环 return 0; }