我知道可以使用 DFS 和 BFS 在直接图中检测循环。我想知道我们是否可以使用Union-Find检测有向图中的循环？
- 如果是，那么如何？和
- 如果我们不能，那为什么？
问问题
5402 次
2 回答
29
不，我们不能使用 union-find 来检测有向图中的循环。这是因为无法使用不相交集（执行并集查找的数据结构）来表示有向图。
当我们说“a union b”时，我们无法确定边缘的方向
- 是a去b吗？（或者）
- b会去a吗？
但是，在无序图的情况下，每个连接的组件都等效于一个集合。所以 union-find 可以用来检测一个循环。每当您尝试对属于同一连通分量的两个顶点执行联合时，我们可以说存在循环。
于 2020-04-25T06:32:02.913 回答
11
不。
让我给你举个例子：
- Q1。取一个无向图：
上面的无向图中是否存在循环？是的。我们可以使用 Union-Find 算法找到循环。
- Q2。现在看类似的有向图：
上述有向图中是否存在循环？不！但是，如果您使用 Union-Find 算法来检测上述有向图中的循环，它会说是！由于 union-find 算法如下图所示：
或者
上图中有循环吗？是的！但是最初的（Q2）问题被篡改了，这不是被问到的。所以联合查找算法会给有向图错误的结果。
于 2020-12-16T02:52:52.440 回答