10

「パス圧縮による加重クイック ユニオン」アルゴリズムがあります。

コード：

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[]役立ちますか?

誰かが私のためにこれを明確にすることができますか?

4

4 に答える 4

20

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番目の祖先にのみ到達することを意味します。

ツリーを上ってルートを見つけるときに、ノードを親から祖父母に移動します。これにより、ツリーが部分的に平坦になります。この操作では、ノードがメンバーになっているツリーは変更されないことに注意してください。これが私たちが関心を持っているすべてです。これがパス圧縮手法です。

（ループが正しいことに気づきましたか？ ルートノードであるとwhile(i == id[i])終了します）i

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

コードに文字起こしエラーがあります：

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

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

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

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

于 2012-10-02T19:29:09.530 に答える
1

質問 1. 行 id[i] = id[id[i]]; と言うのは正しくありません。while ループ while(i != id[i]) は、ノード i がルートを指している場合、つまり i == id[i] の場合にのみ停止することがわかります。行 id[i] = id[id[i]]; を使用してノードをルートに向けているものとします。ここで、内側の id[i] はルートです。

質問2。

iz[i] = i; を初期化するのは間違っています。実際には iz[i] = 1; である必要があります。つまり、すべてのノードのサイズは、サイズが 1 であるため、最初は 1 で初期化されます。ユニオン関数では、次の行があることがわかります。および iz[i] += iz[j]; これにより、ルート ノードのサイズが、結合された 2 つのコンポーネントのサイズの合計になるように更新されます。これにより、ノードのサイズが効率的に更新されます。

于 2013-03-27T10:13:16.337 に答える