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

代码：

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[]如何帮助我们知道集合中元素的数量？

有人可以为我澄清这一点吗？

来源

2012-10-02 Aleksei Chepovoi

阅读c/C++中的算法，第1-4部分，robert sedgewick，第1章，很好的解释。 – rendon

首先明白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] = 1; // RIGHT 
    id[i] = i; 
}

iz[i]是在i根的树元素的数量（或者，如果i不是根，那么iz[i]是未定义的）。所以它应该初始化为1，而不是i。最初，每个元素是一个大小为1的单独“单独”树。

来源

2012-10-02 19:29:09

关于路径压缩，这是路径压缩的单程变体，使路径中的每个其他节点指向其祖父（将路径长度减半）。而Two-pass更像是将第二个循环添加到root将每个检查节点的id []设置为根。似乎有关补充。 – RBz

问题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-27 10:13:16

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-23 20:29:54 DML

一两件事这里要注意：

虽然发现当我们正在制作id[i]=id[id[i]]即：使我在其祖父

- 然后id[i]的大小将减少我i，e的大小; iz[id[i]]-=iz[i]

现在，这使得代码完全正确。

我不知道这个，但直觉上我觉得，它的缺席并不会造成问题，因为我们总是比较根的大小。

来源

2017-05-26 07:45:51

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

回答

相关问题