联合/查找数据结构如何应用于Kruskal的算法？

Question

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

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

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

Answer 1

它在Kruskal算法的条目中说明，但是如果边缘连接两棵不同的树，则可以使用联合/查找结构进行测试（通过查找），或者在添加时是否会形成周期。

如果边缘未形成周期并将其添加到生成树，则可以（通过联合）更新相同的结构。