disjoint-sets - Union / Findデータ構造をKruskalのアルゴリズムにどのように適用できますか？

Question

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

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

素集合に使用されているデータ構造の結合/検索...

Answer 1

クラスカルのアルゴリズムのエントリに記載されていますが、union / find構造を使用して、エッジが2つの異なるツリーを接続しているかどうか、または追加されたときにサイクルを形成するかどうかをテストできます（FINDを介して）。

エッジがサイクルを形成せず、スパニングツリーに追加された場合、同じ構造を（UNIONを介して）更新できます。