xsl判断节点存在_判断图中是否有环的两种方法

0 什么是环？

在图论中，环(英语：cycle)是一条只有第一个和最后一个顶点重复的非空路径。

在有向图中，一个结点经过两种路线到达另一个结点，未必形成环。

1 拓扑排序

1.1 无向图

使用拓扑排序可以判断一个无向图中是否存在环，具体步骤如下：

1. 求出图中所有结点的度。
2. 将所有度 <= 1 的结点入队。(独立结点的度为 0)
3. 当队列不空时，弹出队首元素，把与队首元素相邻节点的度减一。如果相邻节点的度变为一，则将相邻结点入队。
4. 循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过，无环；反之，则有环。

1.2 有向图

使用拓扑排序判断无向图和有向图中是否存在环的区别在于：

• 在判断无向图中是否存在环时，求的是结点的度；
• 在判断有向图中是否存在环时，求的是结点的入度。

2 DFS

使用 DFS 可以判断一个无向图和有向中是否存在环。深度优先遍历图，如果在遍历的过程中，发现某个结点有一条边指向已访问过的结点，并且这个已访问过的结点不是上一步访问的结点，则表示存在环。

我们不能仅仅使用一个 bool 数组来表示结点是否访问过。规定每个结点都拥有三种状态，白、灰、黑。开始时所有结点都是白色，当访问过某个结点后，该结点变为灰色，当该结点的所有邻接点都访问完，该节点变为黑色。

那么我们的算法可以表示为：如果在遍历的过程中，发现某个结点有一条边指向灰色节点，并且这个灰色结点不是上一步访问的结点，那么存在环。

3 Code

#include #include #include 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   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 <endl; //0，无环 color = vector<int>(n, 0); last = -1; hasCycle = false; dfs(0); cout <endl;  //0，无环 g[0].push_back(3); g[3].push_back(0); cout <endl; //1，有环 color = vector<int>(n, 0); last = -1; hasCycle = false; dfs(0); cout <endl;  //1，有环 return 0;}

References

1. ?环 (图论)
2. ?有向无环图
3. ?判断一个图是否有环及相关 LeetCode 题目
4. ?判断有向图是否存在环的 2 种方法(深度遍历，拓扑排序)