如何用联合查找确定传递关系

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

现在如何确定5是否与使用union-find的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数据结构。最好的实现几乎实现了线性时间，这在实践中被认为是线性算法。