网页给别人做的 网站后续收费,贵阳学网站建设,网站建设和管理专业,WordPress资讯类主题破解0、什么是环#xff1f;在图论中#xff0c;环#xff08;英语#xff1a;cycle#xff09;是一条只有第一个和最后一个顶点重复的非空路径。在有向图中#xff0c;一个结点经过两种路线到达另一个结点#xff0c;未必形成环。1、拓扑排序1.1、无向图使用拓扑排序可以判…0、什么是环在图论中环英语cycle是一条只有第一个和最后一个顶点重复的非空路径。在有向图中一个结点经过两种路线到达另一个结点未必形成环。1、拓扑排序1.1、无向图使用拓扑排序可以判断一个无向图中是否存在环具体步骤如下求出图中所有结点的度。将所有度 1 的结点入队。独立结点的度为 0当队列不空时弹出队首元素把与队首元素相邻节点的度减一。如果相邻节点的度变为一则将相邻结点入队。循环结束时判断已经访问的结点数是否等于 n。等于 n 说明全部结点都被访问过无环反之则有环。1.2、有向图使用拓扑排序判断无向图和有向图中是否存在环的区别在于在判断无向图中是否存在环时是将所有**度 1** 的结点入队在判断有向图中是否存在环时是将所有**入度 0** 的结点入队。感谢 wangweijunshen 指正2、DFS使用 DFS 可以判断一个无向图和有向中是否存在环。深度优先遍历图如果在遍历的过程中发现某个结点有一条边指向已访问过的结点并且这个已访问过的结点不是上一步访问的结点则表示存在环。我们不能仅仅使用一个 bool 数组来表示结点是否访问过。规定每个结点都拥有三种状态白、灰、黑。开始时所有结点都是白色当访问过某个结点后该结点变为灰色当该结点的所有邻接点都访问完该节点变为黑色。那么我们的算法可以表示为如果在遍历的过程中发现某个结点有一条边指向灰色节点并且这个灰色结点不是上一步访问的结点那么存在环。#include iostream
#include queue
#include vector
using namespace std;vectorvectorint g;
vectorint color;
int last;
bool hasCycle;bool topo_sort() {int n g.size();vectorint degree(n, 0);queueint 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 vectorvectorint(n, vectorint());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 vectorint(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 vectorint(n, 0);last -1;hasCycle false;dfs(0);cout hasCycle endl; //1有环return 0;
}
3、Union-Find Set我们可以使用并查集来判断一个图中是否存在环对于无向图来说在遍历边u-v时如果结点 u 和结点 v 的“父亲”相同那么结点 u 和结点 v 在同一个环中。对于有向图来说在遍历边u-v时如果结点 u 的“父亲”是结点 v那么结点 u 和结点 v 在同一个环中。#include algorithm
#include iostream
#include vector
using namespace std;vectorpairint, int g;
vectorint 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 2g.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———2g.push_back(make_pair(1, 2));vectorint().swap(father);for (int i 0; i 3; i) {father.push_back(i);}cout isCyclicUnirectedGraph() endl; //1有环// Directed acyclic graph// 0// / // v v// 1——2vectorpairint, int().swap(g);g.push_back(make_pair(0, 1));g.push_back(make_pair(1, 2));g.push_back(make_pair(0, 2));vectorint().swap(father);for (int i 0; i 3; i) {father.push_back(i);}cout isCyclicDirectedGraph() endl; //0无环// Directed cyclic graph// 0// / ^// v // 1——2g.pop_back();g.push_back(make_pair(2, 0));vectorint().swap(father);for (int i 0; i 3; i) {father.push_back(i);}cout isCyclicDirectedGraph() endl; //1有环return 0;
}
References 环 (图论) 有向无环图 判断一个图是否有环及相关 LeetCode 题目 判断有向图是否存在环的 2 种方法深度遍历拓扑排序
