分離集合データ構造
分離集合/結合探索フォレスト
タイプ多元木
発明された1964
発明者バーナード・A・ギャラーとマイケル・J・フィッシャー
ビッグO記法による時間計算量
手術平均最悪の場合
検索O (α( n )) [ 1 ] (償却済み)O (α( n )) [ 1 ] (償却済み)
入れるO (1) [ 1 ]O (1) [ 1 ]
空間複雑性
空間O ( n ) [ 1 ]O ( n ) [ 1 ]

コンピュータサイエンスにおいて、素集合データ構造（素集合データ構造、または和集合検索データ構造、またはマージ集合検索集合とも呼ばれる）は、素集合（重複しない集合）の集合を格納するデータ構造です。これは、集合を素集合に分割したものを格納することと同等です。このデータ構造は、新しい集合の追加、集合のマージ（それらの和集合に置き換える）、そして集合の代表要素の検索といった操作を提供します。最後の操作により、任意の2つの要素が同じ集合に属するか異なる集合に属するかを効率的に判定できます。

分離集合データ構造を実装する方法はいくつかありますが、実際には、分離集合フォレストと呼ばれる特定の実装と同一視されることが多いです。この特殊なタイプのフォレストは、和集合操作と検索操作をほぼ一定の償却時間で実行します。 n個のノードを持つ分離集合フォレストでのm回の加算、和集合、または検索操作のシーケンスに必要な合計時間はO ( m α( n ))です。ここで、α( n )は非常にゆっくりと増加する逆アッカーマン関数です。分離集合フォレストは操作ごとにこの時間を保証しませんが、各操作は構造を再調整します (ツリー圧縮経由)。その結果、分離集合フォレストは漸近的に最適であり、実質的に効率的です。

分離集合データ構造は、グラフの最小全域木を求めるクラスカルのアルゴリズムにおいて重要な役割を果たします。最小全域木の重要性は、分離集合データ構造が幅広いアルゴリズムをサポートしていることを意味します。さらに、これらのデータ構造は、記号計算やコンパイラ、特にレジスタ割り当て問題にも応用されています。

歴史

分離集合フォレストは、1964 年にBernard A. GallerとMichael J. Fischerによって初めて説明されました。 [ 2 ] 1973 年に、その時間計算量はの反復対数に制限され、HopcroftとUllmanによって制限されました。[ 3 ] 1975 年に、Robert Tarjan が、アルゴリズムの時間計算量の(逆アッカーマン関数) 上限を初めて証明しました。 [ 4 ]彼はまた、それが厳密であることを証明しました。1979 年に、彼はこれがGaller-Fischer 構造を含むポインタ アルゴリズムなどの特定のクラスのアルゴリズムの下限であることを示しました。 [ 5 ] 1989 年に、FredmanとSaks は、ビットの (償却) ワードは任意の分離集合データ構造ごとに操作ごとにアクセスする必要があることを示しました。 [ 6 ]お（ログ∗⁡（n））{\displaystyle O(\log ^{*}(n))}n{\displaystyle n}お（メートルα（n））{\displaystyle O(m\alpha (n))}Ω（α（n））{\displaystyle \Omega (\alpha (n))}お（ログ⁡n）{\displaystyle O(\log n)}

1991年にガリルとイタリアーノは分離集合のデータ構造の調査を発表しました。[ 7 ]

1994年、リチャード・J・アンダーソンとヘザー・ウォルは、ブロックを必要としないUnion-Findの並列化バージョンを説明した。[ 8 ]

2007年、シルヴァン・コンションとジャン＝クリストフ・フィリアトルは、分離集合フォレストデータ構造の半永続版を開発し、証明支援ツールRocq（当時はCoq）を用いてその正しさを形式化しました。[ 9 ]「半永続」とは、構造の以前のバージョンは効率的に保持されるものの、以前のバージョンのデータ構造にアクセスすると、それ以降のバージョンは無効になることを意味します。彼らの最速の実装は、非永続アルゴリズムとほぼ同等の効率性を達成しています。彼らは計算量解析を行っていません。

限定されたクラスの問題に対してより優れた性能を発揮する、分離集合データ構造の変種も検討されている。ガボウとタージャンは、可能な和集合が特定の方法で制限されている場合、真に線形時間アルゴリズムが可能であることを示した。[ 10 ]特に、「和集合木」が事前に与えられていれば、線形時間を達成できる。これは、集合のすべての要素を含む木である。p[ v ]を木における親とすると、和集合演算は、あるvに対してunion ( v ,p[ v ])という形式をとる必要があるという仮定が成り立つ。

表現

このセクションと次のセクションでは、分離集合データ構造の最も一般的な実装である、 親ポインタツリーのフォレストについて説明します。この表現はガラー・フィッシャー木として知られています。

分離セット フォレスト内の各ノードは、ポインターと、サイズまたはランク (両方ではない) などの補助情報で構成されます。ポインターは、親ポインター ツリーを作成するために使用されます。親ポインターツリーでは、ツリーのルートではない各ノードがその親を指します。ルート ノードを他のノードと区別するために、親ポインターには、ノードへの循環参照やセンチネル値などの無効な値が含まれます。各ツリーはフォレストに格納されているセットを表し、セットのメンバーはツリー内のノードです。ルート ノードはセットの代表を提供します。2 つのノードが同じセットに含まれるのは、そのノードを含むツリーのルートが等しい場合のみです。

フォレスト内のノードは、アプリケーションにとって都合の良い方法で保存できますが、一般的な手法は配列に保存することです。この場合、親は配列のインデックスで指定できます。配列の各エントリは、親ポインター用にΘ(log n )ビットのストレージを必要とします。エントリの残りの部分には、同等かそれ以下のストレージが必要となるため、フォレストを保存するために必要なビット数はΘ( n log n )です。実装で固定サイズのノードを使用する場合（これにより、保存できるフォレストの最大サイズが制限されます）、必要なストレージはnに比例します。

オペレーション

分離セット データ構造は、新しい要素を含む新しいセットの作成、特定の要素を含むセットの代表の検索、および 2 つのセットのマージという 3 つの操作をサポートします。

新しいセットを作る

このMakeSet操作は、新しい要素のみを含む新しい集合に新しい要素を追加し、その新しい集合をデータ構造に追加します。データ構造を集合の分割と見なすと、このMakeSet操作は新しい要素を追加することで集合を拡大し、新しい要素のみを含む新しい部分集合に新しい要素を配置することで既存の分割を拡張します。

分離集合フォレストでは、MakeSetノードの親ポインタとノードのサイズまたはランクを初期化します。ルートが自身を指すノードで表される場合、要素の追加は次の擬似コードで記述できます。 

関数MakeSet( x )は、 x がフォレスト内に存在しない場合、x .parent := x x .size := 1 // ノードがサイズを格納する場合、x .rank := 0 // ノードがランクを格納する場合、 end if end function

この操作は線形時間計算量を持ちます。特に、n個のノードを持つ分離集合フォレストの初期化にはO ( n )の 時間が必要です。

ノードに親が割り当てられていない場合、そのノードはフォレスト内に存在しないことを意味します。

実際には、x をMakeSet保持するためのメモリ割り当て操作が先行する必要があります。メモリ割り当てが、優れた動的配列実装と同様に、償却定数時間操作である限り、ランダムセットフォレストの漸近的なパフォーマンスは変化しません。

セット代表を見つける

この操作は、指定されたクエリノードxFindから親ポインタの連鎖を辿り、ルート要素に到達します。このルート要素はxが属する集合を表し、 x自身である場合もあります。 到達したルート要素を返します。 Find

操作を実行することは、Findフォレストを改善する重要な機会となります。操作の時間Findは親ポインタの追跡に費やされるため、ツリーが平坦であればFind操作は高速化されます。 a がFind実行されると、各親ポインタを順にたどるよりも速くルートに到達する方法はありません。ただし、この検索中に参照される親ポインタは、ルートに近い位置を指すように更新できます。ルートへの途中で参照されるすべての要素は同じセットの一部であるため、フォレストに格納されているセットは変更されません。ただし、Findクエリノードとルートの間にあるノードだけでなく、その子孫に対しても、将来の操作が高速化されます。この更新は、分離セットフォレストの償却パフォーマンス保証の重要な部分です。

漸近的に最適な時間計算量を達成するアルゴリズムはいくつかあります。パス圧縮Findと呼ばれるアルゴリズム群は、クエリノードとルートノードの間にあるすべてのノードをルートノードに向けます。パス圧縮は、次のように単純な再帰を用いて実装できます。 

関数Find( x )は、x .parent ≠ xの場合、x .parent := Find( x .parent ) を返し、そうでない場合はxを返します。

この実装は2つのパス、つまりツリーを1つ上へ、もう1つ下へ移動します。クエリノードからルートまでのパスを格納するのに十分なスクラッチメモリが必要です（上記の擬似コードでは、パスはコールスタックを使用して暗黙的に表現されています）。両方のパスを同じ方向に実行することで、メモリ使用量を一定量に減らすことができます。この定数メモリ実装では、クエリノードからルートまで2回移動します。1回はルートを見つけるため、もう1回はポインタを更新するためです。 

関数Find( x )はroot  := xであり、root .parent ≠ rootである。root  := root .parent を実行すれば、x .parent ≠ root のときに、 parent  := x .parent x .parent := root x  := parentを実行します。ルート終了関数を返す

TarjanとVan LeeuwenはFind、最悪のケースにおける複雑さはそのままに、実用上はより効率的なワンパスアルゴリズムも開発しました。 [ 4 ] これらはパス分割とパス半減と呼ばれます。どちらも、クエリノードとルートノード間のパス上にあるノードの親ポインタを更新します。 パス分割は、そのパス上にあるすべての親ポインタを、そのノードの祖父母へのポインタに置き換えます。 

関数Find( x )は、x .parent ≠ xの間、 do ( x , x .parent) := ( x .parent, x .parent.parent) を実行し、xを返して関数を終了します。

パスの半分化も同様に動作しますが、他のすべての親ポインターのみを置き換えます。 

関数Find( x )は、x .parent ≠ xの間、 x .parent := x .parent.parent x  := x .parent を実行し、 xを返しながら関数を終了します。

2つのセットを結合する

MakeSet8 つのシングルトンを作成します。
のいくつかの操作の後Union、いくつかのセットがグループ化されます。

この操作は、 x を含む集合とyを含む集合をそれらの和集合に置き換えます。 まず、xとyを含む木の根を決定するためにを使用します。根が同じであれば、それ以上何もする必要はありません。そうでない場合は、2つの木をマージする必要があります。これは、xの根の親ポインタをyの根に設定するか、 yの根の親ポインタをxの根に設定することで行われます。 Union(x, y)UnionFind

どのノードを親ノードにするかの選択は、ツリーに対する将来の操作の複雑さに影響を与えます。不注意に選択すると、ツリーが過度に高くなる可能性があります。例えば、xUnionを含むツリーを常にyを含むツリーのサブツリーにするとします。要素で初期化したばかりのフォレストから、, , ...,を実行します。結果として得られるフォレストには、ルートがnである単一のツリーが含まれ、 1 からnへのパスはツリー内のすべてのノードを通過します。このフォレストの実行時間はO ( n )です。 1、2、3、…、n、{\displaystyle 1,2,3,\ldots ,n,}Union(1, 2)Union(2, 3)Union(n - 1, n)Find(1)

効率的な実装では、木の高さはサイズによる結合またはランクによる結合によって制御されます。どちらの方法でも、ノードは親ノードへのポインタ以外の情報を保存する必要があります。この情報は、どのルートが新しい親ノードになるかを決定するために使用されます。どちらの戦略も、木が深くなりすぎないようにします。

規模による連合

サイズによる結合の場合、ノードはそのサイズ、つまり子孫の数（ノード自身を含む）を保持します。ルートxとyを持つツリーを結合する場合、子孫の数が多い方のノードが親になります。2つのノードの子孫の数が同じ場合は、どちらが親になることもできます。どちらの場合も、新しい親ノードのサイズは、新しい子孫の総数に設定されます。 

function Union( x , y )は// ノードをルートに置き換えるx  := Find( x ) y  := Find( y ) x = y の場合return // x と y はすでに同じ集合内にあるend if// 必要であれば、変数を交換して、x が少なくとも y と同じ数の子孫を持つようにします。if x .size < y .size then ( x , y ) := ( y , x ) end if// x を新しいルートにするy .parent := x // x のサイズを更新するx .size := x .size + y .size 関数の終了

サイズを格納するために必要なビット数は、明らかにnを格納するために必要なビット数です。これにより、フォレストに必要なストレージ容量に定数倍が追加されます。

階級別組合

ランクによる結合では、ノードはその高さの上限であるランクを格納します。ノードが初期化されると、ランクは 0 に設定されます。ルートxとyを持つツリーをマージするには、まずそれらのランクを比較します。ランクが異なる場合、ランクの大きい方のツリーが親になり、xとyのランクは変わりません。ランクが同じ場合、どちらが親になることもできますが、新しい親のランクは 1 ずつ増加します。ノードのランクは明らかにその高さに関連していますが、高さを格納するよりもランクを格納する方が効率的です。ノードの高さはFind操作中に変わることがあるため、ランクを格納することで高さを正確に保つための余分な労力を省くことができます。疑似コードでは、ランクによる結合は次のようになります。 

function Union( x , y )は// ノードをルートに置き換えるx  := Find( x ) y  := Find( y ) x = y の場合return // x と y はすでに同じ集合内にあるend if// 必要であれば、変数名を変更して、x のランクが y のランク以上になるようにします。if x .rank < y .rank then ( x , y ) := ( y , x ) end if// x を新しいルートにするy .parent := x // 必要であれば、x のランクをインクリメントするif x .rank = y .rank then x .rank := x .rank + 1 end if end function

すべてのノードはランク以下であることが示される。 [ 11 ]したがって、各ランクはO (log log n )ビット で格納でき、すべてのランクはO ( n log log n )ビットで格納できる。これにより、ランクはフォレストのサイズに対して漸近的に無視できるほど小さい割合となる。 ⌊ログ⁡n⌋{\displaystyle \lfloor \log n\rfloor }

上記の実装から明らかなように、ノードがツリーのルートでない限り、ノードのサイズとランクは重要ではありません。ノードが子ノードになると、そのサイズとランクは再びアクセスされることはありません。

Unionユーザーが形成された集合の代表値を決定するという操作 のバリエーションがあります。この機能を上記のアルゴリズムに追加しても、効率性を損なうことなく容易に実現できます。

時間計算量

Find親ポインタを更新せず、Union木の高さを制御しない分離集合フォレスト実装では、高さがO ( n )のツリーを持つことができます。このような状況では、Findと のUnion操作にはO ( n ) の処理時間がかかります。

実装がパス圧縮のみを使用する場合、n回のMakeSet操作のシーケンスの後に最大n − 1回のUnion操作とf回のFind操作が続く場合、最悪の場合の実行時間は0になります。[ 11 ]Θ（n+f⋅（1+ログ2+f/n⁡n））{\displaystyle \Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))}

ランクによる結合を使用し、実行中に親ポインタを更新しない場合、任意のタイプのm個の操作（最大n個の操作）Findの実行時間は になります。[ 11 ]Θ（メートルログ⁡n）{\displaystyle \Theta (m\log n)}MakeSet

パスの圧縮、分割、半分化と、サイズまたはランクによる結合を組み合わせると、最大n個の演算を含む任意のタイプのm個の演算の実行時間が に短縮されます。[ 4 ] [ 5 ] これにより、各演算の償却実行時間は になります。これは漸近的に最適であり、すべての分離セットのデータ構造では、演算ごとに償却時間を使用する必要があります。[ 6 ] ここで、関数 は逆アッカーマン関数です。逆アッカーマン関数は非常にゆっくりと増加するため、この係数は、物理的宇宙に実際に記述できる任意のnに対して4以下になります。これにより、分離セット演算は実質的に償却定数時間になります。 MakeSetΘ（メートルα（n））{\displaystyle \Theta (m\alpha (n))}Θ（α（n））{\displaystyle \Theta (\alpha (n))}Ω（α（n））{\displaystyle \Omega (\alpha (n))}α（n）{\displaystyle \alpha (n)}

Union-Findの計算量O(m log* n)の証明

分離集合フォレストの性能を正確に分析するのはやや複雑です。しかし、n個のオブジェクトを含む分離集合フォレストにおける任意のmFind個の操作の償却時間はO ( m log * n )であることが証明される、はるかに単純な分析があります。ここで、log *は反復対数を表します。[ 12 ] [ 13 ] [ 14 ] [ 15 ]Union

補題 1: find 関数がルートに沿ってパスをたどるにつれて、遭遇するノードのランクが増加します。

証拠

データセットに Find 操作と Union 操作を適用しても、この事実は時間の経過とともに変わりません。各ノードが自身のツリーのルートである場合、これは自明です。ノードのランクが変化する可能性があるのは、Union by Rank操作が適用された場合のみです。この場合、ランクの低いツリーがランクの高いツリーに接続され、その逆は発生しません。また、Find 操作中は、パスに沿って訪問されるすべてのノードがルートに接続されます。ルートのランクは子ノードよりも高いため、この操作によってもこの事実は変わりません。

補題2: ランクrのサブツリーのルートであるノードuには少なくともノードがある。 2r{\displaystyle 2^{r}}

証拠

各ノードが自身の木の根である場合、これは自明です。ランクrのノードuには少なくとも2 r個のノードがあると仮定します。ランクrの2つの木をUnion by Rank演算で結合すると、ランクr + 1の木が生成され、その根には少なくともノードが含まれます。 2r+2r＝2r+1{\displaystyle 2^{r}+2^{r}=2^{r+1}}

補題3: ランクrのノードの最大数は、n2r。{\displaystyle {\frac {n}{2^{r}}}.}

証拠

補題2から、ランクrの部分木の根ノードuには少なくとも個のノードがあることが分かる。ランクrのノードの最大数は、ランクrの各ノードがちょうど個のノードを持つ木の根ノードであるときである。この場合、ランクrのノードの数は2r{\displaystyle 2^{r}}2r{\displaystyle 2^{r}}n2r。{\displaystyle {\frac {n}{2^{r}}}.}

実行中の任意の時点で、グラフの頂点をランクに応じて「バケット」にグループ化できます。バケットの範囲は、次のように帰納的に定義します。バケット0にはランク0の頂点が含まれます。バケット1にはランク1の頂点が含まれます。バケット2にはランク2と3の頂点が含まれます。一般に、B番目のバケットに区間 のランクを持つ頂点が含まれる場合、(B+1)番目のバケットには区間 のランクを持つ頂点が含まれます。[r、2r−1]＝[r、R−1]{\displaystyle \left[r,2^{r}-1\right]=[r,R-1]}[R、2R−1]。{\displaystyle \left[R,2^{R}-1\right].}

の場合、 とします。すると、バケットには区間 内のランクを持つ頂点が存在します。 B∈北{\displaystyle B\in \mathbb {N} }タワー（B）＝22⋯2⏟B 回{\displaystyle {\text{tower}}(B)=\underbrace {2^{2^{\cdots ^{2}}}} _{B{\text{ 回}}}}B{\displaystyle B}[タワー（B−1）、タワー（B）−1]{\displaystyle [{\text{タワー}}(B-1),{\text{タワー}}(B)-1]}

結合の証明を見つけるお（ログ∗⁡n）{\displaystyle O(\log^{*}n)}

バケットのサイズについては 2 つの点に留意できます。

  1. バケットの合計数は最大でlog * nです。
    証明: 頂点のランクは より大きいことはできないため、頂点を持つことができるのは最初のバケットのみです。ここで、 は上で定義した関数の逆を表します。n{\displaystyle n}ログ∗⁡（n）{\displaystyle \log^{*}(n)}ログ∗{\displaystyle \log^{*}}タワー{\displaystyle {\text{タワー}}}
  2. バケット内の要素の最大数は です。 [B、2B−1]{\displaystyle \left[B,2^{B}-1\right]}2n2B{\displaystyle {\frac {2n}{2^{B}}}}
    証明: バケット内の要素の最大数は最大で[B、2B−1]{\displaystyle \left[B,2^{B}-1\right]}n2B+n2B+1+n2B+2+⋯+n22B−1≤2n2B。{\displaystyle {\frac {n}{2^{B}}}+{\frac {n}{2^{B+1}}}+{\frac {n}{2^{B+2}}}+\cdots +{\frac {n}{2^{2^{B}-1}}}\leq {\frac {2n}{2^{B}}}.}

Fは実行された「検索」操作のリストを表し 、

T1＝∑F（ルートへのリンク）{\displaystyle T_{1}=\sum _{F}{\text{(ルートへのリンク)}}}T2＝∑F（バケットが異なるリンクの数）{\displaystyle T_{2}=\sum _{F}{\text{(バケットが異なるリンクの数)}}}T3＝∑F(バケットが同じであるリンクの数)。{\displaystyle T_{3}=\sum _{F}{\text{(バケットが同じであるリンクの数)。}}}

すると、 m個の検索にかかる総コストはT＝T1+T2+T3。{\displaystyle T=T_{1}+T_{2}+T_{3}.}

各検索操作はルートに到達するトラバーサルを1回だけ行うため、T 1 = O ( m )となります。

また、バケットの数に関する上記の境界から、T 2 = O ( m log * n )となります。

T 3では、 uからvへのエッジをトラバースしていると仮定します。ここで、uとv はバケット[ B、 2 B − 1]内でランクを持ち、vはルートではありません (このトラバースの時点ではルートではありません。そうでなければ、トラバースはT 1で考慮されます)。u を固定し、さまざまな検索操作でvの役割を果たすシーケンスを検討します。パス圧縮とルートへのエッジを考慮していないため、このシーケンスには異なるノードのみが含まれ、補題 1により、このシーケンス内のノードのランクは厳密に増加していることがわかります。両方のノードがバケット内にあるため、シーケンスの長さk (ノードu が同じバケット内の異なるルートに接続されている回数) は、バケットB内のランクの数以下、つまり、最大でv1、v2、…、vけ{\displaystyle v_{1},v_{2},\ldots ,v_{k}}2B−1−B<2B。{\displaystyle 2^{B}-1-B<2^{B}.}

したがって、T3≤∑[B、2B−1]∑あなた2B。{\displaystyle T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.}

観察1と2から、次のように結論づけられる。T3≤∑B2B2n2B≤2nログ∗⁡n。{\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}

したがって、T＝T1+T2+T3＝お（メートルログ∗⁡n）。{\displaystyle T=T_{1}+T_{2}+T_{3}=O(m\log^{*}n).}

その他の構造

操作あたりの最悪ケース時間の短縮

ランクによる結合または重みによる結合を持つFind木における 操作の最悪時間は（つまり であり、この境界は厳密である）である。1985 年に、N. Blum はパス圧縮を使用せず、 の間に木を圧縮する 操作の実装を示した。彼の実装は操作あたり 時間で実行されるため、[ 16 ] Galler と Fischer の構造と比較すると、操作あたりの最悪時間は短縮されるが、償却時間は短縮される。1999 年に、Alstrup らは、逆アッカーマン償却時間とともに最悪時間が最適となる構造を示した。 [ 17 ]Θ（ログ⁡n）{\displaystyle \Theta (\log n)}お（ログ⁡n）{\displaystyle O(\log n)}あなたn私on{\displaystyle ユニオン}お（ログ⁡n/ログ⁡ログ⁡n）{\displaystyle O(\log n/\log \log n)}お（ログ⁡n/ログ⁡ログ⁡n）{\displaystyle O(\log n/\log \log n)}

削除

通常の分離集合フォレストの実装では、要素の削除に対してあまり反応しません。つまり、Find要素数の減少によって の時間が短縮されないということです。しかし、定数時間の削除を可能にし、 の時間制限が現在の要素数Findに依存する現代的な実装も存在します[ 18 ] [ 19 ]

バックトラッキング

特定の分離集合フォレスト構造を拡張してバックトラッキングを可能にすることが可能です。バックトラッキングの基本的な形式は、 Backtrack(1)最後の を元に戻す操作を許可することですUnion。より高度な形式では、最後の i 個の結合を元に戻す が許可されます。次のような計算量の結果が知られています。操作ごとに と をサポートし、 とをBacktrack(i)サポートするデータ構造があります。[ 20 ]この結果において、 が形成された集合の代表を選択する自由度が不可欠です。分離可能なポインタアルゴリズムのクラスでは、より短い償却時間を実現することはできません。[ 20 ]UnionFindお（ログ⁡n/ログ⁡ログ⁡n）{\displaystyle O(\log n/\log \log n)}Backtrackお（1）{\displaystyle O(1)}Union

アプリケーション

クラスカルのアルゴリズムを使用して最小全域木を見つけるときの Union-Find のデモ。

分離集合データ構造は、集合の分割をモデル化します。例えば、無向グラフの連結成分を追跡するために使用されます。このモデルは、2つの頂点が同じ成分に属しているかどうか、あるいはそれらの間に辺を追加すると閉路になるかどうかを判定するために使用できます。Union-Findアルゴリズムは、ユニフィケーションの高性能実装で使用されます。[ 21 ]

このデータ構造は、Boost GraphライブラリのIncremental Connected Components機能を実装するために使用されます。また、グラフの 最小全域木を求めるKruskalアルゴリズムを実装するための重要なコンポーネントでもあります。

Hoshen -Kopelman アルゴリズムでは、アルゴリズム内で Union-Find を使用します。

参照

  • パーティションの改良、つまり、ばらばらのセットを維持するための異なるデータ構造で、セットを結合するのではなく分割する更新を行う。
  • 動的接続性 - グラフの接続コンポーネントに関する情報を保持するデータ構造

参考文献

  1. ^ a b c d e f Tarjan, Robert Endre (1975). 「線形集合結合アルゴリズムの効率性」Journal of the ACM . 22 (2): 215– 225. doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID  11105749 .
  2. ^ Galler, Bernard A. ; Fischer, Michael J. (1964年5月). 「改良された同値アルゴリズム」 . Communications of the ACM . 7 (5): 301– 303. doi : 10.1145/364099.364331 . S2CID 9034016 . . 分離集合フォレストの論文。
  3. ^ Hopcroft, JE ; Ullman, JD (1973). 「セットマージアルゴリズム」. SIAM Journal on Computing . 2 (4): 294– 303. doi : 10.1137/0202024 .
  4. ^ a b c Tarjan, Robert E. ; van Leeuwen, Jan (1984). 「集合和集合アルゴリズムの最悪ケース解析」 . Journal of the ACM . 31 (2): 245– 281. doi : 10.1145/62.2160 . S2CID 5363073 . 
  5. ^ a b Tarjan, Robert Endre (1979). 「非線形時間で分離集合を維持しなければならないアルゴリズムのクラス」 . Journal of Computer and System Sciences . 18 (2): 110– 127. doi : 10.1016/0022-0000(79)90042-4 .
  6. ^ a b Fredman, M. ; Saks, M. (1989年5月). 「動的データ構造のセルプローブ複雑度」.第21回ACMコンピューティング理論シンポジウム - STOC '89 議事録. pp.  345– 354. doi : 10.1145/73007.73040 . ISBN 0897913078. S2CID  13470414 .定理5:集合結合問題の任意のCPROBE(log n )実装では、 n個のシングルトン集合から始めて、 m回のFindとn −1回のUnionを実行するのにΩ( m α( m , n ))時間が必要です。
  7. ^ Galil, Z.; Italiano, G. (1991). 「素集合和問題のためのデータ構造とアルゴリズム」. ACM Computing Surveys . 23 (3): 319– 344. doi : 10.1145/116873.116878 . S2CID 207160759 . 
  8. ^ Anderson, Richard J.; Woll, Heather (1994).ユニオン探索問題に対する待機不要の並列アルゴリズム. 第23回ACM計算理論シンポジウム. pp.  370– 380. doi : 10.1145/103418.103458 .
  9. ^ Conchon, Sylvain; Filliâtre, Jean-Christophe (2007年10月). 「永続的なUnion-Findデータ構造」. ACM SIGPLAN Workshop on ML . フライブルク、ドイツ.
  10. ^ Harold N. Gabow, Robert Endre Tarjan, 「非結合集合和の特殊なケースに対する線形時間アルゴリズム」, Journal of Computer and System Sciences, Volume 30, Issue 2, 1985, pp. 209–221, ISSN 0022-0000, https://doi.org/10.1016/0022-0000(85)90014-5
  11. ^ a b cコーメン, トーマス・H. ;レイソン, チャールズ・E. ;リベスト, ロナルド・L. ;スタイン, クリフォード(2009). 「第21章 非素集合のデータ構造」.アルゴリズム入門（第3版）. MITプレス. pp.  571– 572. ISBN 978-0-262-03384-8。
  12. ^ライムンド・ザイデル、ミカ・シャリル「パス圧縮のトップダウン分析」、SIAM J. Comput. 34(3):515–525、2005
  13. ^ Tarjan, Robert Endre (1975). 「線形ではないが優れた集合結合アルゴリズムの効率」 . Journal of the ACM . 22 (2): 215– 225. doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID 11105749 . 
  14. ^ Hopcroft, JE; Ullman, JD (1973). 「セットマージアルゴリズム」. SIAM Journal on Computing . 2 (4): 294– 303. doi : 10.1137/0202024 .
  15. ^ Robert E. TarjanとJan van Leeuwen . 集合和アルゴリズムの最悪ケース解析. ACMジャーナル, 31(2):245–281, 1984.
  16. ^ Blum, Norbert (1985). 「分離集合和問題における単一演算の最悪ケース時間計算量について」.第2回シンポジウム. コンピュータサイエンスの理論的側面について: 32–38 .
  17. ^ Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis (1999). 「union-findにおける最悪ケースおよび償却最適性（拡張アブストラクト）」.第31回ACM計算理論シンポジウム論文集. pp.  499– 506. doi : 10.1145/301250.301383 . ISBN 1581130678. S2CID  100111 .
  18. ^アルストラップ、スティーブン;ソープ、ミッケル。ゲルツ、インゲ・リー;ラウエ、タイス。ズウィック、ウリ (2014)。 「一定の時間削除による結合検索」。アルゴリズムに関する ACM トランザクション。11 (1): 6:1–6:28。土井：10.1145/2636922。S2CID 12767012。 
  19. ^ Ben-Amram, Amir M.; Yoffe, Simon (2011). 「単純かつ効率的なUnion-Find-Deleteアルゴリズム」.理論計算機科学. 412 ( 4–5 ): 487– 492. doi : 10.1016/j.tcs.2010.11.005 .
  20. ^ a b Westbrook, Jeffery R.; Tarjan, Robert E. (1989). 「バックトラッキングによる集合和集合のアルゴリズムの償却分析」SIAM Journal on Computing . 18 (1): 1– 11. doi : 10.1137/0218001 .
  21. ^ナイト、ケビン (1989). 「統合：学際的サーベイ」(PDF) . ACM Computing Surveys . 21 : 93–124 . doi : 10.1145/62029.62030 . S2CID 14619034 . 
「 https://en.wikipedia.org/w/index.php?title=Disjoint-set_data_structure&oldid=1331814179」より取得