我们可以使用 Union-Find 数据结构检测有向图中的循环吗？

Question

我知道可以使用 DFS 和 BFS 检测直接图中的循环。我想知道我们是否可以使用Union-Find检测有向图中的循环？

• 如果是，那么如何？和
• 如果我们不能，那为什么？

Answer 1

不，我们不能使用 union-find 来检测有向图中的循环。这是因为无法使用不相交集（执行联合查找的数据结构）来表示有向图。

当我们说“a union b”时，我们无法确定边的方向

1. a 要去 b 吗？（或者）
2. b 要去 a 吗？

但是，在无序图的情况下，每个连接的组件等效于一个集合。所以 union-find 可以用来检测循环。每当您尝试对属于同一连接组件的两个顶点执行并集时，我们可以说存在循环。

Answer 2

不。

让我给你举个例子：

• 一季度。取一个无向图：

上面的无向图中有环吗？是的。我们可以使用 Union-Find 算法找到循环。

• Q2。现在看类似的有向图：

上面有向图中有环吗？不！但是如果你使用 Union-Find 算法来检测上面有向图中的循环，它会说是！由于 union-find 算法查看上图如下：

或者

上图中有环吗？是的！但是最初的（Q2）问题被篡改了，这不是被问到的。因此 Union-find 算法会对有向图给出错误的结果。