マツシタのお勉強

Union-Findを用いて2つの要素が同じ集合に属してるかを高速で判定する

Union-Findとは

Union-Findとは、2つの要素が同じ集合に属しているか否かを高速で判定することを実現するデータ構造である。Union−Findは、様々な実装パターンが存在するが木構造を用いた物を考える。また、Union-Findはその名前からも分るように以下の2つの操作がある。

  • Find: あるノードのルートを取得する
  • Union: ある2つの木を結合する

この2つのメソッドをもったクラスとなる。これらの操作を用いて実用的な様々な判定を行う事ができる。代表的なものは、2つのノードが同じ木に属しているかを判定するものだ。 また、2つの木の結合時にそれぞれの持つ値(木の大きさや何らかの重み)も一緒に加算し、ルートに保持させておく事で、あるノードが属してる木の状態を高速に取得することができる。

Find

Findは引数にノードのインデックスを与えることで、与えたノードが属する木のルートのインデックスを返すようにする。

① → ② → ③ という木が存在した時に、find(3) //=> 1という具合だ。具体的な実装は最後に記す。

Union

Unionは引数に結合させたい2つのノードのインデックスを与えることで、それぞれが属する木を結合させるようにする。

① → ② → ③, ④ → ⑤ という2つの木が存在した時に、union(2, 5)とすると、

① → ② → ③

④ → ⑤

という具合に接続される。

Union-Findのルール

Union-Findには、いくつかルールが存在する。以下にまとめる

  • 2つの木を結合する場合、木の高さが小さい木が大きい木のルートに直接接続する
  • 結合はできるが分割はできない

それぞれ詳しく見ていく

2つの木を結合する場合、木の高さが小さい木が大きい木のルートに直接接続する

結合する場合は、結合されて出来上がる木の高さがなるべく小さくなるように結合する。あるノードをFindする際、そのノードの根まで辿り、どの木であるか判定する。この時に木の高さの分だけ計算量がかかってしまうので、なるべく木の高さが低くなるようにUnionしていく必要がある。これによってFindの計算量は約O(logN) (N: ノードの数)となる。

結合はできるが分割はできない

Union-Findは分割はできないという制約を持っているので、複数回の結合がある場合は、分割が必要にならないような順番で結合をしていかなければならない。具体的には以下の通りだ。

Union-Findを使用する場合、初めは全てのノードは別々の木(大きさ1)に属し、Unionの操作でそれぞれ結合されていく。 Unionの操作では全てのノードが結合可能というわけではなく、問題の条件によって結合できない場合がある。よって、結合する条件が厳しい順に結合することで、後々に分割する必要は無くなる。

例えば、Aさんは、①, ②, ③全てのノードが結合可能という条件で、Bさんは①, ②のみ結合可能だとする。この時、Aさんから操作を行うと、全てのノードが結合可能なので、出来上がる木は② ← ① → ③となる。次にBさんの操作を行う場合、① → ② の木を作りたい。しかし、既に①、②、③を含んだ木が出来てしまっている。Union-Findは分割が出来ないので、再び初めから木を作り直さなければならない。これでは計算量が無駄にかかってしまう。よって、結合条件が厳しいBから操作する事で、分割や木の作り直しの必要がなくなり、効率良く操作を行う事が可能になる。

Union-Find Tree の実装