如何使用 union-find 确定传递关系
How to determine transitive relation with union-find
我有以下数据集
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 相关？有人请指导我。
您不必在此处使用 Union-Find。您可以使用基本 DFS 标记一个连接组件中每个访问的顶点，并使用您在此组件中开始 DFS 的顶点的索引。此方法在输入大小方面是线性的，因此它总是比 Union-Find.
的任何实现都快
但是，如果您想按 Union-Find 完成，对于输入中的每个边 x-y，请调用 Union(x, y)。在处理完所有的边之后，如果你想知道一个顶点 a 是否与 a 顶点 b 相关，即是否存在由以 a 开头的边连接的顶点序列并且以 b 结尾，只需检查是否 Find(a) == Find(b)。此方法的复杂性取决于您如何实现 Union-Find 数据结构。最好的实现几乎是线性时间，在实践中被认为是线性算法。
我有以下数据集
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 相关？有人请指导我。
您不必在此处使用 Union-Find。您可以使用基本 DFS 标记一个连接组件中每个访问的顶点，并使用您在此组件中开始 DFS 的顶点的索引。此方法在输入大小方面是线性的，因此它总是比 Union-Find.
但是，如果您想按 Union-Find 完成，对于输入中的每个边 x-y，请调用 Union(x, y)。在处理完所有的边之后，如果你想知道一个顶点 a 是否与 a 顶点 b 相关，即是否存在由以 a 开头的边连接的顶点序列并且以 b 结尾，只需检查是否 Find(a) == Find(b)。此方法的复杂性取决于您如何实现 Union-Find 数据结构。最好的实现几乎是线性时间，在实践中被认为是线性算法。