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

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]]意味着我们只到达节点的第二个ancester,而不是root.

2. iz[]包含整数0到N-1.如何iz[]帮助我们了解集合中的元素数量？

有人可以为我澄清一下吗？

Answer 1

首先要明白这id是一片森林.id[i]是...的父母i.如果id[i] == i它意味着它i是一个根.

对于某些根i(where 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]]意味着我们只到达节点的第二个ancester,而不是root.

当我们提升树找到根时,我们将节点从父母移动到他们的祖父母.这部分地使树变平.请注意,此操作不会更改节点所属的树,这是我们感兴趣的全部内容.这是路径压缩技术.

(你确实注意到循环正确吗？ 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]是以root 为根的树的元素数i(或者如果i不是根则iz[i]是未定义的).所以它应该初始化为1,而不是i.最初,每个元素都是一个单独的"单例"树1.

Answer 2

id [i] = id [id [i]]; //这一行表示"路径压缩"

上面的代码是"简单的一次通过变量",如Union Find(Algorithms,第一部分,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