algorithm - 如何使用 union-find 确定传递关系

Question

我有以下数据集

6 - 7  -->means 6 and 7 are related
5 - 4  -->means 5 and 4 are related
4 - 6  -->means 4 and 6 are related

现在如何使用 union-find 确定 5 是否与 7 相关？有人请指导我。

Answer 1

你不必在这里使用Union-Find。您可以使用基本的 DFS 标记一个连接组件中每个访问的顶点，并使用您在该组件中开始 DFS 的顶点的索引。此方法在输入大小方面是线性的，因此它总是比 Union-Find 的任何实现都快。

但是，如果您想通过 Union-Find 来完成，对于输入中的每条边 x-y，调用 Union(x, y)。在处理完所有的边之后，如果你想找出一个顶点 a 是否与 a 顶点 b 相关，即是否存在由以 开头的边连接的顶点序列a 并以 b 结尾，只需检查是否 Find(a) == Find(b)。此方法的复杂性取决于您如何实现 Union-Find 数据结构。最佳实现时间几乎是线性的，这在实践中被认为是线性算法。