我们可以使用Union-Find数据结构检测有向图中的周期吗？ [英] Can we detect cycles in directed graph using Union-Find data structure?
问题描述
我知道可以使用DFS和BFS在直接图中检测周期。我想知道是否可以使用 Union-Find 检测有向图中的循环？
I know that one can detect cycles in direct graphs using DFS and BFS. I want to know whether we can detect cycles in directed graphs using Union-Find or not?
- 如果是， ，那又如何？和
- 如果不能，为什么？
推荐答案
否，我们不能使用联合查找来检测有向图中的循环。这是因为不能使用不交集（执行联合查找的数据结构）表示有向图。
No, we cannot use union-find to detect cycles in a directed graph. This is because a directed graph cannot be represented using the disjoint-set(the data structure on which union-find is performed).
当我们说联合b时我们无法确定边缘的方向
When we say 'a union b' we cannot make out the direction of edge
- 是去b了吗？ （或）
- b是要去a吗？
但是，在无序图的情况下，每个连接的组件都等同于一个集合。因此，工会发现可以用来检测一个周期。每当您尝试在属于同一连接组件的两个顶点上执行合并时，我们都可以说存在该循环。
But, incase of unordered graphs, each connected component is equivalent to a set. So union-find can be used to detect a cycle. Whenever you try to perform union on two vertices belonging to the same connected component, we can say that cycle exists.
这篇关于我们可以使用Union-Find数据结构检测有向图中的周期吗？的文章就介绍到这了，希望我们推荐的答案对大家有所帮助，也希望大家多多支持IT屋！
