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

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

（您确实注意到循环对吗？ 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 回答
8

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

于 2014-10-23T20:29:54.230 回答
2

这里还要注意一件事：

在我们做id[i]=id[id[i]]ie的时候找根；让我在它的祖父母之下

- 然后大小id[i]将减少 ii,e 的大小；iz[id[i]]-=iz[i]

现在这使代码完全正确。

我对此不确定，但直觉上我觉得，它的缺失不会引起问题，因为我们总是在比较根的大小。

于 2017-05-26T07:45:51.050 回答
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[j] += iz[i]; 和 iz[i] += iz[j]; 它将根节点的大小更新为连接在一起的两个组件的大小之和。这有效地更新了节点大小。

于 2013-03-27T10:13:16.337 回答