私はthe wiki pageを読んでいます。なぜ小さなリストを大きなものに追加するのが重要なのか理解できません。ここでユニオンの理解を見つける
はwikiページからアルゴリズムの部分である：
は、あなたがリストのコレクションを持っており、各リスト の各ノードは、それが属するオブジェクト、リストの名前が含まれているとそのリスト内の要素の数は です。また、すべてのリスト内の 要素の合計数がn（つまり、全体でn個の要素）であると仮定します。 これらのリストのいずれか2つをマージし、 が属しているリストの名前が依然として含まれるように、 のすべてのノードを更新したいと考えています。リストAとBをマージするルールは、 AがBより大きい場合は、Bの要素をAにマージし、 はBに属していた要素を更新し、その逆も同様です。
これは、リストのいずれかの要素すべてを繰り返し処理し、ラベルを変更する更新操作を実行する単純な方法を示しています。
小さいリストを繰り返し処理する方が速くなるので、小さい方のリストを大きなものにマージするのが理にかなっています。
wikiページでは、より長いリストが重要ではなくなったばらばらの集合データ構造に対してはるかに効率的な方法を説明しています。
ユニオン検索は、あなたが誰かをいくつかのセットの「リーダー」に保つための単なる方法です。
あなたはこのようにそれをコーディングすることができますので、たとえば、あなたは5人A、B、C、D、E
があると最初はそれぞれが、独自のセットで開始：
for each person in people:
dad[person] = person
この方法で、すべての人を自分のセットのリーダーにすることができます。
これは、それがどのように見えるかされています
{A} {B} {C} {D} {E}
私たちが必要とする最初の操作は、セットのリーダーを見つけることができるようにすることであり、この操作はfindと呼ばれています。
私たちはプロパティになります：リーダーは自分のお父様である人です。
2つの可能性がありますが、その人は自分の父親か、そうでない人です。
あれば、セットのリーダーです。
もしそうでなければ、私たちは同じことを（それが自分の父親であれば）父親に尋ねて行きます。
あなたはこのようにそれをコーディングすることができますし、我々はunion操作を持って
find_leader_of(person P){
if(dad[P] == P) return P
else return find_leader_of(dad[P])
}
、それは一組だけで2つのdisjointsセットを回すよりも、より多くの何もありません。
は、あなたがこのような状況があるとします。
{A, B} {C, D} {E}
を、あなたがunion(B, D)を行い、その後、何が起こりますか？
まずあなたが両方のセットのリーダーを見つける必要があります。
fst_leader = find_leader_of(B)
snd_leader = find_leader_of(D)
を、あなたは他のリーダーになるために、これらの指導者のいずれかを選択します。
dad[snd_leader] = fst_leader
と、これは、その結果：
union(person P1, person P2){
fst_leader = find_leader_of(P!)
snd_leader = find_leader_of(P2)
dad[snd_leader] = fst_leader
}
には、誰が誰のリーダーになるかを選ぶための組合発見や他の方法を改善するための他のアプローチがありますが、これは組合の発見が何であるかを知るために理解しなければならない基本です。
単純なアプローチを使いたい場合を除いて、Hoshen-Kopelmanアルゴリズムhttps://www.ocf.berkeley.edu/~fricke/projects/hoshenkopelman/hoshenkopelman.htmlを見てみるとよいでしょう。ここでは、N * Aの累積された複雑さを持ちます。ここで、Aは逆Ackerman関数です。定数6）。言い換えれば、WICKED FASTです。
私が間違っていないと、多くの人がツリーを折りたたんだとき、つまり最も効率的なときに、全体的な効率を見てきました。私はそれらの研究にあなたを指摘することはできませんが、私は10年前にテキストブックでそれらを読むことを覚えています。
これが役に立ちます。