互いに素な集合のデータ構造

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

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

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

歴史

互いに素な集合の森は、1964年にバーナード・A・ギャラーとマイケル・J・フィッシャーによって初めて記述されました。 ^{[ 2 ]} 1973年には、その時間計算量は制限されました。 $O(\log ^{*}(n))$ の反復対数 $n$ ホップクロフトとウルマンによる。^{[ 3 ]} 1975年、ロバート・タージャンは、 $O(m\alpha (n))$ （逆アッカーマン関数）アルゴリズムの時間計算量の上限。^{[ 4 ]}彼はまた、それがタイトであることを証明した。1979年、彼はこれがガラー・フィッシャー構造を含む特定のクラスのアルゴリズム、ポインタアルゴリズムの下限であることを示した。^{[ 5 ]} 1989年、フレッドマンとサックスは、 $\Omega (\alpha (n))$ （償却された）言葉 $O(\log n)$ ビットは、操作ごとに任意の非連結集合データ構造によってアクセスされなければならない^{[ 6 ]。}これにより、このモデルにおけるデータ構造の最適性が証明される。

1991年、ガリルとイタリアーノは、互いに素な集合のデータ構造に関する調査を発表した。^{[ 7 ]}

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

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

限定されたクラスの問題でより優れたパフォーマンスを発揮する、互いに素な集合データ構造の変種も検討されています。Gabow と Tarjan は、可能な和集合が特定の方法で制限されている場合、真に線形時間のアルゴリズムが可能であることを示しました。^{[ 10 ]}特に、「和集合木」が事前に与えられている場合は、線形時間を実現できます。これは、集合のすべての要素を含む木です。p[ v ] を木の親とすると、和集合演算は、あるvに対してunion ( v , p[ v ])の形式である必要があるという仮定があります。

表現

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

互いに素な集合の森の各ノードは、ポインタと補助情報（サイズまたはランクのいずれか、ただし両方ではない）で構成されます。ポインタは親ポインタツリーを作成するために使用され、ツリーのルートではない各ノードは親を指します。ルートノードを他のノードと区別するために、親ポインタには、ノードへの循環参照や番兵値などの無効な値があります。各ツリーは、森に格納されている集合を表し、集合のメンバーはツリー内のノードです。ルートノードは集合の代表を提供します。2 つのノードが同じ集合に属するのは、それらのノードを含むツリーのルートが等しい場合のみです。

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

業務

互いに素な集合のデータ構造は、次の3つの操作をサポートします。新しい要素を含む新しい集合を作成する。指定された要素を含む集合の代表要素を見つける。2つの集合をマージする。

新しいセットを作成する

このMakeSet操作では、新しい要素のみを含む新しいセットに新しい要素が追加され、その新しいセットがデータ構造に追加されます。データ構造をセットの分割とみなす場合、このMakeSet操作は新しい要素を追加することでセットを拡大し、新しい要素のみを含む新しい部分セットに新しい要素を追加することで既存の分割を拡張します。

互いに素な集合の森では、MakeSetノードの親ポインタとノードのサイズまたはランクを初期化します。ルートが自身を指すノードで表される場合、要素の追加は次の擬似コードを使用して記述できます。

function MakeSet( x ) is if x is not already in the forest then x .parent := x x .size := 1 // ノードがサイズを格納する場合x .rank := 0 // ノードがランクを格納する場合end if end function

この操作は線形時間計算量を持つ。特に、 $n個の$ ノードを持つ互いに素な集合の森を初期化するには $O (n)の$ 時間が必要となる。

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

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

集合の代表者を見つける

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

操作を実行することは、Findフォレストを改善する重要な機会となります。Find操作にかかる時間は親ポインタを追跡することに費やされるため、ツリーがフラットであればあるほどFind操作は速くなります。Find操作を実行する際、各親ポインタを順番にたどる以外にルートに到達する最速の方法はありません。しかし、この探索中に訪問した親ポインタは、ルートにより近い方向を指すように更新できます。ルートへの経路で訪問したすべての要素は同じセットの一部であるため、これによりフォレストに格納されているセットは変更されません。しかし、Findクエリノードとルートの間のノードだけでなく、それらの子孫ノードについても、今後の操作が速くなります。この更新は、非連結セットフォレストの償却パフォーマンス保証の重要な部分です。

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

function Find( x ) is if x .parent ≠ x then x .parent := Find( x .parent) return x .parent else return x end if end function

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

function Find( x ) is root := x while root .parent ≠ root do root := root .parent end whilewhile x.parent ≠ root do parent := x.parent x.parent := root x : = parent end whileルートエンド関数を返す

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

function Find( x ) is while x .parent ≠ x do ( x , x .parent) := ( x .parent, x .parent.parent) end while return x end function

パスの半減も同様に機能しますが、親ポインタを一つおきに置き換えるだけです。

function Find( x ) is while x .parent ≠ x do x .parent := x .parent.parent x := x .parent end while return x end function

2つのセットをマージする

MakeSet8つのシングルトンを作成します。

いくつかの操作の後Union、いくつかの集合がグループ化されます。

この操作では、 $x$ を含む集合と $y$ を含む集合を、それらの和集合に置き換えます。まず、 $x$ と $y$ を含むツリーのルートを決定します。ルートが同じであれば、それ以上何もする必要はありません。そうでなければ、2 つのツリーをマージする必要があります。これは、 $x$ のルートの親ポインタを $y$ の親ポインタに設定するか、 $yのルートの親ポインタを$ $x$ の親ポインタに設定することによって行われます。Union(x, y)UnionFind

どのノードを親にするかという選択は、ツリーに対する今後の操作の複雑さに影響を及ぼします。不用意に選択すると、ツリーが過度に高くなる可能性があります。たとえば、 $x$ Unionを含むツリーを $y$ を含むツリーのサブツリーに常にすると仮定します。要素で初期化されたばかりのフォレストから始めます。 $1,2,3,\ldots ,n,$ そして、、、、、を実行しますUnion(1, 2)。Union(2, 3)結果として得られるフォレストには、ルートが $n$ である単一の木が含まれ、1 から $n$ へのパスは木内のすべてのノードを通過します。このフォレストの実行時間は $O$ $($ $n$ $)$ です。Union(n - 1, n)Find(1)

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

サイズ別組合

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

function Union( x , y ) is // ノードをルートに置き換えるx := Find( x ) y := Find( y ) if x = y then 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 end function

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

階級による組合

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

function Union( x , y ) is // ノードをルートに置き換えるx := Find( x ) y := Find( y ) if x = y then 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

すべてのノードにはランクがあることが示せる。 $\lfloor \log n\rfloor$ またはそれ以下。^{[ 11 ]} $その結果、各ランクはO (log log n)$ ビットに格納でき、すべてのランクは $O (n log log n)$ ビットに格納できます。これにより、ランクはフォレストのサイズの漸近的に無視できる部分になります。

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

ユーザーが生成された集合の代表値を指定する操作のバリエーションも存在するUnion。この機能は、効率を損なうことなく上記のアルゴリズムに追加することは難しくない。

時間計算量

Find親ポインタを更新せず、Union木の高さを制御しようとしない、互いに素な集合の森の実装では、高さが $O (n)$ の木を持つことができます。このような状況では、FindおよびUnion操作には $O (n) の$ 時間が必要です。

実装がパス圧縮のみを使用する場合、 $n 回$ MakeSetの操作、それに続く最大 $n - 1 回$ Unionの操作、そして $f 回の$ Find操作のシーケンスの最悪実行時間は $\Theta (n+f\cdot \left(1+\log _{2+f/n}n\right))$ [ ¹¹^]

ランクによる結合を使用するが、その間親ポインタを更新しない場合Find、実行時間は次のようになる。 $\Theta (m\log n)$ $任意のタイプのm$ 個の操作に対して、そのうち $n 個$ までがMakeSet操作である。^{[ 11 ]}

パス圧縮、分割、または半分化と、サイズまたはランクによる結合の組み合わせにより、 $m$ 個の任意のタイプの操作の実行時間が短縮されます。そのうち $n$ MakeSet個は操作です。 $\Theta (m\alpha (n))$ [ ⁴^]^[⁵^] これにより、^各操作の償却実行時間が $\Theta (\alpha (n))$ これは漸近的に最適であり、つまりすべての非連結集合データ構造はこれを使用する必要がある。 $\Omega (\alpha (n))$ 操作ごとの償却時間。^{[ 6 ]} ここで、関数 $\alpha (n)$ は逆アッカーマン関数です。逆アッカーマン関数は非常にゆっくりと増加するため、この係数は、物理世界で実際に記述できる任意の $nに対して$ $4$ 以下になります。これにより、互いに素な集合の操作は実質的に償却定数時間になります。

Union-Find の時間計算量が O(m log* n) であることの証明

互いに素な集合の森のパフォーマンスを正確に分析することはやや複雑です。しかし、 $n$ 個のオブジェクトを含む互いに素な集合の森に対する任意の $m$ Find回の操作の償却時間は $O$ $($ $m$ $log$ $*$ $n$ $)$ であることを証明する、はるかに単純な分析があります。ここで、 $log$ $*$ は反復対数を表します。^[¹²^]^[¹³^]^[¹⁴^]^[¹⁵^]Union

補題１：find関数がルートに向かってパスをたどるにつれて、遭遇するノードのランクは増加する。

証拠

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

$補題2：ランクr$ のサブツリーのルートであるノード $u$ は、少なくとも $2r$ ノード。

証拠

最初は各ノードが自身の木の根である場合、これは自明に真です。ランク $r$ のノード $u が$ 少なくとも $2$ $r$ 個のノードを持つと仮定します。すると、ランク $rの 2 つの木が$ 「ランクによる結合」操作を使用してマージされると、ランク $r$ $+ 1$ の木が生成され、その根は少なくとも 2 r 個のノードを持ちます。 $\displaystyle 2^{r}+2^{r}=2^{r+1}}$ ノード。

$補題3：ランクr$ のノードの最大数は最大で ${\frac {n}{2^{r}}}.$

証拠

補題2より、ランク $r$ のサブツリーのルートであるノード $u$ は少なくとも $2r$ $ノード。ランクr$ の各ノードが、正確にを持つ木の根である場合、ランク $r$ のノードの最大数が得られます。 $2r$ $ノード。この場合、ランクr$ のノード数は ${\frac {n}{2^{r}}}.$

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

のために $B\in \mathbb {N}$ 、させて $\displaystyle \text{tower}}(B)=\underbrace {2^{2^{\cdots ^{2}}}} _{B{\text{ 回}}}}$ .それからバケット $B$ 区間内のランクを持つ頂点を持つ $[{\text{tower}}(B-1),{\text{tower}}(B)-1]$ 。

{\displaystyle O(\log ^{*}n)} — 証明 $O(\log ^{*}n)$ ユニオンファインド

バケツの大きさに関して、2つの点が観察できる。

バケットの総数は最大で $log * n$ です。
証明: どの頂点もランクが以下より大きくなることはないので $n$ 最初のものだけ $\log ^{*}(n)$ バケットには頂点があり、 $\displaystyle \log ^{*}}$ の逆を表します ${\text{タワー}}$ 上記で定義された関数。
バケット内の要素の最大数 $\left[B,2^{B}-1\right]$ 最大で ${\frac {2n}{2^{B}}}$ 。
証明：バケット内の要素の最大数 $\left[B,2^{B}-1\right]$ 最大で ${\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$ は実行された「find」操作のリストを表し、

$T_{1}=\sum _{F}{\text{(ルートへのリンク)}}$ $T_{2}=\sum _{F}{\text{(バケットが異なるリンクをたどった回数)}}$ $T_{3}=\sum _{F}{\text{(バケットが同じであるリンクをたどった回数)}}$

$すると、 m 個$ の合計コストは $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},v_{2},\ldots ,v_{k}$ $異なる検索操作でv$ の役割を果たすノード。パス圧縮とルートへのエッジを考慮しないことから、このシーケンスには異なるノードのみが含まれており、補題 1により、このシーケンスのノードのランクは厳密に増加していることがわかります。両方のノードがバケット内にあることから、シーケンスの長さ $k (ノード$ $u$ が同じバケット内の異なるルートに接続されている回数) は、バケット $B$ のランクの数以下、つまり最大で $2^{B}-1-B<2^{B}.$

したがって、 $T_{3}\leq \sum _{[B,2^{B}-1]}\sum _{u}2^{B}.$

観察1と2から、次のことが結論付けられる。 ${\textstyle T_{3}\leq \sum _{B}2^{B}{\frac {2n}{2^{B}}}\leq 2n\log ^{*}n.}$

したがって、 $T=T_{1}+T_{2}+T_{3}=O(m\log ^{*}n).$

その他の建造物

操作ごとの最悪ケース時間の改善

ランクによる結合または重量による結合を行うFindツリーにおける操作の最悪ケース時間は $\Theta (\log n)$ （つまり、それは $O(\log n)$ そしてこの境界はタイトです）。1985年、N. Blumはパス圧縮を使用しないが、ツリーを圧縮する操作の実装を提供しました。 $union$ 彼の実装は $O(\log n/\log \log n)$ 1回の操作あたりの時間^{[ 16 ]}は、GallerとFischerの構造と比較すると、1回の操作あたりの最悪ケース時間は優れているが、償却時間は劣る。1999年、Alstrupらは、最悪ケース時間が最適な構造を提示した。 $O(\log n/\log \log n)$ 逆アッカーマン償却時間と併せて。^{[ 17 ]}

削除

通常の実装では、要素の削除に対して好ましい反応は示さず、Find要素数の減少によって実行時間が改善されることはありません。しかし、定数時間での削除を可能にし、実行時間が現在の要素数Findに依存する最新の実装が存在します^[¹⁸^]^[¹⁹^]。

後戻り

特定の非連結集合フォレスト構造を拡張してバックトラッキングを可能にすることは可能です。バックトラッキングの基本形式は、 Backtrack(1)最後の操作を取り消す操作を許可することですUnion。より高度な形式では、最後の i 個の和集合を取り消す操作を許可します。次の複雑性の結果が知られています。とをBacktrack(i)サポートするデータ構造が存在します。UnionFind $O(\log n/\log \log n)$ 操作ごとの時間、Backtrackそして $O(1)$ 時間。^{[ 20 ]}この結果では、形成されたセットの代表を選択する自由が不可欠です。分離可能なポインタアルゴリズムUnionのクラス内では、より優れた償却時間を達成することはできません。^[²⁰^]

アプリケーション

互いに素な集合のデータ構造は、集合の分割をモデル化します。たとえば、無向グラフの連結成分を追跡するために使用します。このモデルは、2 つの頂点が同じ成分に属しているかどうか、またはそれらの間にエッジを追加するとサイクルが発生するかどうかを判断するために使用できます。Union-Find アルゴリズムは、ユニフィケーションの高性能実装で使用されます。^[²¹^]

このデータ構造は、Boost Graph Libraryがインクリメンタル連結成分機能を実装するために使用されます。また、グラフの最小全域木を求めるクラスカル法を実装する上でも重要な構成要素です。

ホシェン・コペルマンアルゴリズムは、ユニオンファインドを使用します。

ユニオンファインドは、比較的高いパフォーマンスを発揮する型推論アルゴリズムを実装するために使用できる。

参考文献

1 2 3 4 5 6 Tarjan, Robert Endre (1975). "Efficiency of a Good But Not Linear Set Union Algorithm". Journal of the ACM . 22 (2): 215– 225. doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID 11105749 .
↑ Galler, Bernard A. ; Fischer, Michael J. (1964 年 5 月). 「改良された等価性アルゴリズム」 . Communications of the ACM . 7 (5): 301–303 . doi : 10.1145/364099.364331 . S2CID 9034016 . 互いに素な集合の森を提唱した論文。
↑ Hopcroft, JE ; Ullman, JD (1973). "Set Merging Algorithms". SIAM Journal on Computing . 2 (4): 294– 303. doi : 10.1137/0202024 .
1 2 3 Tarjan, Robert E. ; van Leeuwen, Jan (1984). "Worst-case analysis of set union algorithms" . Journal of the ACM . 31 (2): 245–281 . doi : 10.1145/62.2160 . S2CID 5363073 .
1 2 Tarjan, Robert Endre (1979). "A class of algorithms which require non-linear time to maintain disjoint sets" . Journal of Computer and System Sciences . 18 (2): 110– 127. doi : 10.1016/0022-0000(79)90042-4 .
1 2 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 )) 時間を必要とします。
↑ Galil, Z.; Italiano, G. (1991). "データ構造と、互いに素な集合の和集合問題のためのアルゴリズム". ACM Computing Surveys . 23 (3): 319–344 . doi : 10.1145/116873.116878 . S2CID 207160759 .
↑ Anderson, Richard J.; Woll, Heather (1994). Union-Find 問題に対する待機不要の並列アルゴリズム. 第 23 回 ACM 理論計算機科学シンポジウム. pp. 370–380 . doi : 10.1145/103418.103458 .
↑ Conchon, Sylvain; Filliâtre, Jean-Christophe (2007 年 10 月). 「永続的な Union-Find データ構造」. ACM SIGPLAN 機械学習ワークショップ. ドイツ、フライブルク。
↑ Harold N. Gabow、Robert Endre Tarjan、「互いに素な集合の和集合の特殊なケースに対する線形時間アルゴリズム」、Journal of Computer and System Sciences、第30巻、第2号、1985年、pp. 209–221、ISSN 0022-0000、https://doi.org/10.1016/0022-0000(85) 90014-5
1 2 3 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009). "第21章：互いに素な集合のデータ構造".アルゴリズム入門（第3版）. MIT Press. pp. 571–572 . ISBN 978-0-262-03384-8。
↑ Raimund Seidel、Micha Sharir。「パス圧縮のトップダウン分析」、SIAM J. Comput. 34(3):515–525、2005年
↑ Tarjan, Robert Endre (1975). "Efficiency of a Good But Not Linear Set Union Algorithm" . Journal of the ACM . 22 (2): 215–225 . doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID 11105749 .
↑ Hopcroft, JE; Ullman, JD (1973). "Set Merging Algorithms". SIAM Journal on Computing . 2 (4): 294–303 . doi : 10.1137/0202024 .
↑ Robert E. TarjanおよびJan van Leeuwen。「集合和アルゴリズムの最悪ケース分析」。Journal of the ACM、31(2):245–281、1984 年。
↑ Blum, Norbert (1985). 「互いに素な集合の和集合問題の単一操作の最悪時間計算量について」。第2回コンピュータサイエンスの理論的側面に関するシンポジウム: 32–38。
↑ Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis (1999). "Worst-case and amortised optimality in union-find (Extended abstract)". Proceedings of the thirty-first annual ACM symposium on Theory of Computing . pp. 499–506 . doi : 10.1145/301250.301383 . ISBN 1581130678. S2CID 100111 .
↑アルストラップ、スティーブン;ソープ、ミッケル。ゲルツ、インゲ・リー;ラウエ、タイス。ズウィック、ウリ (2014)。「一定の時間削除による結合検索」。アルゴリズムに関する ACM トランザクション。11 (1): 6:1–6:28。土井：10.1145/2636922。S2CID 12767012。
↑ Ben-Amram, Amir M.; Yoffe, Simon (2011). "A simple and efficient Union-Find-Delete algorithm". Theoretical Computer Science . 412 ( 4– 5): 487– 492. doi : 10.1016/j.tcs.2010.11.005 .
1 2 Westbrook, Jeffery R.; Tarjan, Robert E. (1989). "バックトラッキング付き集合和アルゴリズムの償却分析". SIAM Journal on Computing . 18 (1): 1– 11. doi : 10.1137/0218001 .
↑ Knight, Kevin (1989). "Unification: A multidisciplinary survey" (PDF) . ACM Computing Surveys . 21 : 93– 124. doi : 10.1145/62029.62030 . S2CID 14619034 .

外部リンク

Boost C++ライブラリの一部であるC++実装
Java実装、 JGraphTライブラリの一部
JavaScriptによる実装
Pythonによる実装

[tarjan1975-1] 1 2 3 4 5 6 Tarjan, Robert Endre (1975). "Efficiency of a Good But Not Linear Set Union Algorithm". Journal of the ACM . 22 (2): 215– 225. doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID 11105749 .

[Galler1964-2] Galler, Bernard A. ; Fischer, Michael J. (1964 年 5 月). 「改良された等価性アルゴリズム」 . Communications of the ACM . 7 (5): 301–303 . doi : 10.1145/364099.364331 . S2CID 9034016 . 互いに素な集合の森を提唱した論文。

[Hopcroft1973-3] Hopcroft, JE ; Ullman, JD (1973). "Set Merging Algorithms". SIAM Journal on Computing . 2 (4): 294– 303. doi : 10.1137/0202024 .

[Tarjan1984-4] 1 2 3 Tarjan, Robert E. ; van Leeuwen, Jan (1984). "Worst-case analysis of set union algorithms" . Journal of the ACM . 31 (2): 245–281 . doi : 10.1145/62.2160 . S2CID 5363073 .

[Tarjan1979-5] 1 2 Tarjan, Robert Endre (1979). "A class of algorithms which require non-linear time to maintain disjoint sets" . Journal of Computer and System Sciences . 18 (2): 110– 127. doi : 10.1016/0022-0000(79)90042-4 .

[Fredman1989-6] 1 2 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 )) 時間を必要とします。

[Galil1991-7] Galil, Z.; Italiano, G. (1991). "データ構造と、互いに素な集合の和集合問題のためのアルゴリズム". ACM Computing Surveys . 23 (3): 319–344 . doi : 10.1145/116873.116878 . S2CID 207160759 .

[Anderson1994-8] Anderson, Richard J.; Woll, Heather (1994). Union-Find 問題に対する待機不要の並列アルゴリズム. 第 23 回 ACM 理論計算機科学シンポジウム. pp. 370–380 . doi : 10.1145/103418.103458 .

[Conchon2007-9] Conchon, Sylvain; Filliâtre, Jean-Christophe (2007 年 10 月). 「永続的な Union-Find データ構造」. ACM SIGPLAN 機械学習ワークショップ. ドイツ、フライブルク。

[10] Harold N. Gabow、Robert Endre Tarjan、「互いに素な集合の和集合の特殊なケースに対する線形時間アルゴリズム」、Journal of Computer and System Sciences、第30巻、第2号、1985年、pp. 209–221、ISSN 0022-0000、https://doi.org/10.1016/0022-0000(85) 90014-5

[Cormen2009-11] 1 2 3 Cormen, Thomas H. ; Leiserson, Charles E. ; Rivest, Ronald L. ; Stein, Clifford (2009). "第21章：互いに素な集合のデータ構造".アルゴリズム入門（第3版）. MIT Press. pp. 571–572 . ISBN 978-0-262-03384-8。

[12] Raimund Seidel、Micha Sharir。「パス圧縮のトップダウン分析」、SIAM J. Comput. 34(3):515–525、2005年

[13] Tarjan, Robert Endre (1975). "Efficiency of a Good But Not Linear Set Union Algorithm" . Journal of the ACM . 22 (2): 215–225 . doi : 10.1145/321879.321884 . hdl : 1813/5942 . S2CID 11105749 .

[14] Hopcroft, JE; Ullman, JD (1973). "Set Merging Algorithms". SIAM Journal on Computing . 2 (4): 294–303 . doi : 10.1137/0202024 .

[15] Robert E. TarjanおよびJan van Leeuwen。「集合和アルゴリズムの最悪ケース分析」。Journal of the ACM、31(2):245–281、1984 年。

[16] Blum, Norbert (1985). 「互いに素な集合の和集合問題の単一操作の最悪時間計算量について」。第2回コンピュータサイエンスの理論的側面に関するシンポジウム: 32–38。

[17] Alstrup, Stephen; Ben-Amram, Amir M.; Rauhe, Theis (1999). "Worst-case and amortised optimality in union-find (Extended abstract)". Proceedings of the thirty-first annual ACM symposium on Theory of Computing . 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). "A simple and efficient Union-Find-Delete algorithm". Theoretical Computer Science . 412 ( 4– 5): 487– 492. doi : 10.1016/j.tcs.2010.11.005 .

[WT-20] 1 2 Westbrook, Jeffery R.; Tarjan, Robert E. (1989). "バックトラッキング付き集合和アルゴリズムの償却分析". SIAM Journal on Computing . 18 (1): 1– 11. doi : 10.1137/0218001 .

[Knight1989-21] Knight, Kevin (1989). "Unification: A multidisciplinary survey" (PDF) . ACM Computing Surveys . 21 : 93– 124. doi : 10.1145/62029.62030 . S2CID 14619034 .

[ 2 ]

[ 3 ]

[ 4 ]

[ 5 ]

[ 6 ]。

[ 7 ]

[ 8 ]

[ 9 ]

[ 10 ]

[ 11 ]

[

[

[

[

[ 16 ]

[ 17 ]

[

[

[ 20 ]

[

歴史

表現

業務