まず、2つのパス圧縮写真を見てみましょう。
ユニオンファインドセットは非常に繊細で実用的なデータ構造であり、主に一部の非交差セットのマージの問題に対処するために使用されます。いくつかの一般的な用途には、サブグラフの接続、最小スパニングツリーを見つけるためのKruskalアルゴリズム、および最も一般的な祖先(LCA)が含まれます。
セットを使用して検索すると、最初に一連のDisjoint Dynamicセットs = {s 1、s 2、⋯、s k}があります。これは、整数を使用してセットの要素を表すために使用します。
各セットには1つ以上の要素が含まれている場合があり、セット内の要素が代表として選択されます。各セットにどの要素が含まれているかを気にすることは重要ではなく、どの要素が代表として選択されるかを気にすることは重要ではありません。私たちが気にしているのは、特定の要素について、この要素が配置されているセット(表現)をすばやく見つけることができ、2つの要素が位置するセットと、これらの操作の時間の複雑さが一定であることです。
チェックとコレクションには3つの基本操作があります。
Makeet(s):Sシングルエレメントセットを含む新しい検索セットを作成します。
Unionset(x、y):要素xと要素yが位置するセットをマージし、xとyが位置するセットが交差せず、交差する場合、統合しないことを要求します。
find(x):要素xが配置されているセットの代表を見つけます。この操作は、2つの要素が同じセットにあるかどうかを判断するためにも使用できます。それぞれの代表者を比較するだけです。
パッケージcom.datastructure.union_find; //第5版のユニオンフィンドパブリッククラスUnionfind5 {// rank [i]は、後続のコードでi //で根付いたセットで表されるツリーのレイヤー数を表します。ランクのセマンティクスを維持しません。これは、Private Int []ランクの比較の標準にすぎません。 private int []親; //親[i]は、i番目の要素のprivate int countを指す親ノードを表します。 //データの数// Constructor Public UnionFind5(int count){rank = new int [count];親= new int [count]; this.count = count; //初期化、各親はそれ自体を指し、各要素が(int i = 0; i <count; i ++){parent [i] = i;の独自のセットを形成することを示します。ランク[i] = 1; }} //検索プロセス、要素p // o(h)の複雑さに対応するセット番号を見つけます、hはツリープライベートint find(int p){assert(p> = 0 && p <count); //パス圧縮1 while(p!= parent [p]){parent [p] = parent [parent [p]]; p =親[p]; } purny p; //パス圧縮2、再帰アルゴリズム// if(p!= parent [p])// parent [p] = find(parent [p]); // return parent [p]; } //要素Pと要素qがセットに属するかどうかを確認します} //要素Pと要素qが属するセットをマージします// o(h)の複雑さ、hはツリーパブリックボイドユニオンセメントの高さ(int p、int q){int prot = find(p); int qroot = find(q); if(prot == qroot)return; // 2つの要素が配置されているツリー内の異なる要素の数に基づいてマージ方向を判断します// [ランク] <ランク[QROOT]){parent [prot] = qRoot; } else if(rank [qroot] <rank [prot]){parent [qroot] = prot; } else {// rank [prot] == rank [qroot] parent [prot] = qroot;ランク[QROOT] += 1; //この時点で、私はランクの価値を維持します}}}}要約します
上記は、Javaプログラミングの実装とコレクションに関するこの記事のパス圧縮コードのすべての詳細な説明です。私はそれが誰にでも役立つことを願っています。興味のある友人は、このサイトの他の関連トピックを引き続き参照できます。欠点がある場合は、それを指摘するためにメッセージを残してください。このサイトへのご支援をありがとうございました!