Union/Find數據結構如何應用於Kruskal算法？

Question

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

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

聯盟/查找被用於不相交集合數據結構，...

Answer 1

它在Kruskal算法該項記錄中，但你可以使用union /查找結構測試（通過FIND）如果邊緣連接兩棵不同的樹，或者它會在添加時形成一個循環。

如果邊緣沒有形成周期並且被添加到生成樹中，則可以更新（通過UNION）相同的結構。