パス圧縮アルゴリズム付き加重クイックユニオン

Question

「パス圧縮付き加重クイック連合」アルゴリズムがあります。

コード：

public class WeightedQU 
{ 
    private int[] id; 
    private int[] iz; 

    public WeightedQU(int N) 
    { 
     id = new int[N]; 
     iz = new int[N]; 
     for(int i = 0; i < id.length; i++) 
     { 
      iz[i] = i; 
      id[i] = i; 
     } 
    } 

    public int root(int i) 
    { 
     while(i != id[i]) 
     { 
      id[i] = id[id[i]]; // this line represents "path compression" 
      i = id[i]; 
     } 
     return i; 
    } 

    public boolean connected(int p, int q) 
    { 
     return root(p) == root(q); 
    } 

    public void union(int p, int q) // here iz[] is used to "weighting" 
    { 
     int i = root(p); 
     int j = root(q); 
     if(iz[i] < iz[j]) 
     { 
      id[i] = j; 
      iz[j] += iz[i]; 
     } 
     else 
     { 
      id[j] = i; 
      iz[i] += iz[j]; 
     } 
    } 
} 

質問：

1. パス圧縮作業を行う方法は？ id[i] = id[id[i]]は、ルートではなくノードの2番目のアンサーにのみ到達することを意味します。

2. iz[]は、0からN-1までの整数を含みます。 iz[]は、どのようにしてセットの要素数を知るのに役立ちますか？

誰かが私にこれを明確にすることはできますか？

Answer 1

まず、idがフォレストであることを理解してください。 id[i]はiの親です。 id[i] == iの場合は、iがルートであることを意味します。いくつかのルートi（id[i] == i）について

は次にiz[i]はiをルートツリー内の要素の数です。

public int root(int i) 
{ 
    while(i != id[i]) 
    { 
     id[i] = id[id[i]]; // this line represents "path compression" 
     i = id[i]; 
    } 
    return i; 
} 

パス圧縮作業を行う方法は？ id[i] = id[id[i]]は、ルートではなくノードの2番目のアンサーにのみ到達することを意味します。

私たちはルートを見つけるためにツリーを上っているので、ノードを親から祖父母に移動させます。これは部分的に木を平らにする。この操作はノードがどのツリーに属しているかを変更しないことに注意してください。これは私たちが興味を持っているすべてのものです。これはパス圧縮技術です。

（あなたがiがルートノードになると、右？while(i == id[i])が終了ループに気づかなかった）

iz[]が0からN-1に整数が含まれています。 iz[]は、どのようにしてセットの要素数を知るのに役立ちますか？

コードにおける転写エラーがある：

これは正しいバージョンである：

for(int i = 0; i < id.length; i++) 
{ 
    iz[i] = 1; // RIGHT 
    id[i] = i; 
} 

iz[i]はiをルートとするツリーの要素の数（又は場合でありますiはルートではなくiz[i]は未定義です）。だからではなく、に初期化する必要があります。最初の各要素は、サイズ1の別個の「シングルトン」ツリーです。

Answer 2

質問1。 行id [i] = id [id [i]]と言うのは正しいことではありません。ループwhile（i！= id [i]）は、ノードiがルートを指しているとき、つまりi == id [i] .Byのときにのみ停止します。 id [i] = id [id]]という行を使ってノードをルートに向けるはずです。内側のid [i]はルートです。

質問2.

あなたはIZを初期化するために間違っている[I] = I;実際にはiz [i] = 1でなければなりません。つまり、各ノードサイズはサイズが1であるため、最初は1で初期化されます。 ユニオン関数では、iz [j] + = iz [i]という行があることを認識しています。 iz [i] + = iz [j]である。ルートノードのサイズを、一緒に結合された2つのコンポーネントのサイズの合計に更新する。これによりノードサイズが効率的に更新されます。

Answer 3

id [i] = id [id [i]]; //この行は "パス圧縮"を表します

上記のコードはUnion Find（Algorithms、Part I by Kevin Wayne and Robert Sedgewick）のスライドに記載されているように、「シンプルなワンパスバリアント」です。したがって、質問1のあなたの推測は正しいです。調べられた各ノードはその祖父母を指し示している。

は、我々は2パスの実装が必要になりますルートに各検査されたノードポイントを作成するには：

/** 
* Returns the component identifier for the component containing site <tt>p</tt>. 
* @param p the integer representing one site 
* @return the component identifier for the component containing site <tt>p</tt> 
* @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N 
*/ 
public int find(int p) { 
    int root = p; 
    while (root != id[root]) 
     root = id[root]; 
    while (p != root) { 
     int newp = id[p]; 
     id[p] = root; 
     p = newp; 
    } 
    return root; 
} 

参考： http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionPathCompressionUF.java.html

Answer 4

もう一つは、ここで注目される：

を見つけながら私たちが作っているルートはid[i]=id[id[i]]です。私の祖父母の下に私を作る

- サイズのid[i]は、i、eのサイズによって減少します。 iz[id[i]]-=iz[i]

これでコードが完全に正しくなりました。

これはわかりませんが直感的に私は感じます 私たちは常に根のサイズを比較しているので、その不在は問題にはなりません。