java - 带路径压缩算法的加权快速联合

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

How does the path compression work? id[i] = id[id[i]] means that we reach only the second ancester of our node, not the root.

当我们沿着树向上寻找根节点时，我们将节点从它们的父节点移动到它们的祖 parent 节点。这部分压平了树。请注意，此操作不会更改节点是哪棵树的成员，这就是我们感兴趣的全部。这就是路径压缩技术。

(您确实注意到循环了吗？while(i == id[i]) 在 i 是根节点时终止)

iz[] contains integers from 0 to N-1. How does iz[] help us know the number of elements in the set?

代码中存在转录错误:

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 的独立“单例”树。