带路径压缩算法的加权快速并集

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];
        }
    }
}

问题：

>

路径压缩是如何工作的id[i]=id[id[i]]意味着我们只到达节点的第二个祖先，而不是根。

iz[] 包含从 0 到 N-1 的整数。iz[]如何帮助我们知道集合中元素的数量？

有人能帮我澄清一下吗？

Answer 1

这里还有一点需要注意:

当我们创建id[i]=id[id[i]]i；让我在它的祖父母手下

-则 id[i] 的大小将减小 i i，e 的大小;iz[id[i]]-=iz[i]

这使得代码完全正确。

我不确定这一点，但直觉上我觉得，它的缺失不会导致问题，因为我们总是在比较根的大小。

Answer 2

id[i]=id[id[i]]；//这一行表示“路径压缩”

上面的代码是联合查找（Kevin Wayne和Robert Sedgewick的算法，第一部分）幻灯片中提到的“更简单的一次变体”。因此，您对问题1的猜测是正确的。每个被检查的节点都指向它的祖父母。

要使每个被检查的节点指向根，我们需要两次传递实现：

  /**
 * 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 3

首先了解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] 意味着我们只到达节点的第二个祖先，而不是根。

当我们沿着树向上寻找根时，我们将节点从它们的父节点移动到它们的父节点。这部分展平了树。注意，这个操作并没有改变节点是哪个树的成员，这是我们唯一感兴趣的。这就是路径压缩技术。

（你确实注意到了这个循环吗？而（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;
}

< code>iz[i]是以< code>i为根的树的元素数(或者，如果< code>i不是根，则< code>iz[i]未定义)。所以应该初始化为< code>1，而不是< code>i。最初，每个元素是一个大小为< code>1的单独的“单例”树。