disjoint-sets - Union/Find 数据结构如何应用于 Kruskal 算法？

Question

http://en.wikipedia.org/wiki/Disjoint_sets

http://en.wikipedia.org/wiki/Kruskal's_algorithm

用于不相交集的联合/查找数据结构...

Answer 1

在 Kruskal 算法的条目中有说明，但是您可以使用 union/find 结构来测试（通过 FIND）边是否连接两个不同的树，或者添加时是否会形成循环。

如果边不形成循环并添加到生成树中，则可以更新相同的结构（通过 UNION）。