Union Find木 - ゆるゆる雑記帳

蟻本を読んでてわからなかったので、いろいろググったら、やっと簡易版がわかるようになった。

蟻本のpar[x] = Xの所は何を示しているのかというと、par[x]のxは要素そのものであるのに対して、Xは所属グループ・・・つまりノードの親を示している。

簡単な例を書くと、初期化したものは以下のようになる。

par[0] = 0, par[1] = 1, par[2] = 2

rank[0] = 0, rank[1] = 0, rank[2] = 0

初期値の場合、すべてが根になる par[x] == xが根の条件になるので。

ここから、x =0, y=1として結合させると、x = root(0) = 0, y = root(1) = 1となり、par[y=1] = (x=0)となるため、 par[1] = 0となり、要素1は要素0を根とするグループに所属することになる。イメージ：(0) → (1)

root(1)を求めると、root(1) = 0となるため、次のステップでroot(0) = 0となり、1の根が0であることを示している。

x=1, y=2でもう一回結合すると、par[2] = 0となるので、要素2も要素0に所属することになり、ノードは (1) ← (0) → (2) となる。

・・・なるほどね、よくできている。これを考えた人はすごいな。

とりあえず簡易版は理解できたので、次は下のリンク先のものを勉強するとします。