Union-Find Tree を理解する!素集合系を扱うデータ構造

2020年1月18日データ構造競プロ, データ構造, 連結成分, Union-Find

2つの集合が共通する要素を持たない時に「互いに素」であると言い、このような集合の集まりを「素集合系」などと言います。

素集合系
素集合系の例

素集合系は、いくつかの木構造を用いることで管理することができます。1つの集合は1つの木を用いて表現され、各ノードが集合に含まれる元になります。

このような木を Union-find Tree と言います。

Union-find Tree
素集合系の例の時のUnion-find Tree

工夫をすれば、集合に新たな要素を加えるor集合同士をまとめる操作や、同じ集合に要素があるかを判定する操作を\(O(logn)\)よりも高速に行うことができます。

Union-find Tree

Union-find Tree はデータを互いに素な集合(素集合系)にして管理するためのデータ構造です。主に以下の操作が行えます。

  • makeTree(x) : 新しく x を根とした木をつくる
  • findRoot(x) : xを含む木の根(root)を求める。木の根を代表点(representative)と言ったりする。
  • union(x,y) : 指定された2つ要素 x,y を含む木を併合する
  • isSame(x,y) : x,y が同じ木(集合)にあるのかを、根が同じかで判定する

1つの木が、1つの集合を表しています。工夫をすれば、木(集合)同士の併合や、同じ集合に含まれているかの判定は高速にできます。

しかし、一度まとめた集合を分割したり、ノードを削除したりするのにはあまり向いていません。

まずは、なにも工夫しない場合における操作を詳しく見ておきましょう。

makeTree(a)

makeTree(x) によって、新しく a を根とした木をつくることができます。例えば、makeTree(2)では以下のようになります。

makeTree(2)によってできる木

findRoot(x)

findRoot(x)によって、xを含む木の根、つまり代表となる点を求めます。例えば、以下のような木に対してfindRoot(6)を行った場合は、代表点である4を返します

union(x,y)

2つの木をつなげることを考えましょう。以下の図の時を例に考えます。

union(3,5) によって、3を含む木と5を含む木を1つにまとめます。出来上がる木の代表点は、もともとの木の2つの代表点のどちらかになるようにしましょう。

高速化の工夫

先程の実装のように、普通に木を作って何も考えずに併合することを繰り返すと、以下のように木が長くなってしまう可能性があります。

木の高さが頂点数と同じ例
木の高さが頂点数と同じ例

こうなると、例えば findRoot(9) などを行うとき、木の下から順番に全てのノードをたどる必要があるので、頂点数 n に応じた時間がかかってしまい効率が悪くなります。

これを防ぐためには、主に2種類の手法を組み合わせて使います。

  • 経路圧縮findRoot(x)の際にたどった頂点は、全て木の根に直接繋がるようにする
  • 高さ/サイズ による合併union(x,y) の際には、木の高さの低い物(木のサイズが小さい物)を、高い方の木の根(root)に直接つける

どちらか片方だけでも、findRoot(x)isSame(x,y) の計算量が\(O(logn)\)まで高速化できます。

経路圧縮

左図のような木について、findRoot(9)をすることを考えます。下から代表点である2へとたどるついでに、途中の点を全て2へと繋いでしまえば、右図のように木の高さが低くなります。

もとの木
経路圧縮後の木

先程の findRoot(x)を変更して、自身の親を、木の根に更新するコードにしましょう。

この工夫により、計算量が\(O(n)\)から\(O(logn)\)になります。

高さ/サイズ による合併

以下の例において、union(2,5) によって、2を含む木と5を含む木を1つにまとめることを考えましょう。

この時、代表点2の木と代表点5の木のどちらをどちらに繋げるのかで効率が変わってきます。戦略としては主に2種類あって、

  • 木の高さが低い方を高い方へ繋げる
  • 木のサイズ(ノード数)が小さい方を大きい方へ繋げる

どちらの戦略であっても、今回は以下のようになります。

効率的な併合

逆のつなげ方をすると、以下のように木の高さが3になってしまい、計算が非効率になってしまいます。

非効率な併合

木の高さによる更新は以下のようにします。

木のサイズによる更新は以下のようにします。

証明は難しいのでこの記事では詳しく説明しませんが、この工夫により計算量が\(O(n)\)から\(O(logn)\)になります。経路圧縮と合わせると、アッカーマン関数の逆関数\(\alpha\) を用いて、\(O(\alpha(n))\)で計算できることが知られています(\(O(logn)\)よりも高速)。

C++の実装例

union by rank

まずはrankによる併合から。

union by size

サイズによる併合のバージョンです。集合のサイズが分かるという利点があります。

※サイズに関しては root に格納された値しか見ないので、親を格納する配列と1つにまとめることもできます。

練習問題

参考