我有以下数据集
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 相关？有人请指导我。
问问题
125 次
1 回答
1
你不必Union-Find在这里使用。您可以使用基本DFS标记一个连接组件中的每个访问的顶点，并使用您DFS在该组件中开始的顶点的索引。这种方法在输入大小方面是线性的，因此它总是比任何实现都快Union-Find。
但是，如果您想通过 来执行此操作Union-Find，对于输入中的每个边x-y，请调用Union(x, y)。在处理完所有的边之后，如果你想知道一个顶点 a 是否与avertex相关b，即是否有一个由以 开头a和以 结尾的边连接的顶点序列b，只需检查 if Find(a) == Find(b)。此方法的复杂性取决于您如何实现 Union-Find 数据结构。最好的实现几乎是线性时间，这在实践中被认为是线性算法。
于 2015-10-24T13:35:29.660 回答