有一个“加权快速联合路径压缩”算法.
代码:
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 []如何帮助我们知道集合中的元素数量?
有人可以为我解释一下吗
解决方法
首先明白id是森林. id [i]是我的父母.如果id [i] ==我意味着我是一个根.
对于一些根i(其中id [i] == i),则iz [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.
当我们爬树,找到根,我们将节点从他们的父母移到他们的祖父母.这部分地使树变平.请注意,此操作不会更改节点所属的树,这就是我们所感兴趣的所有者,这是路径压缩技术.
(你确实注意到循环是正确的?while(i == id [i])终止一旦我是一个根节点)
iz[]
contains integers from0
toN-1
. How doesiz[]
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]是根据我的树(或如果我不是根,然后iz [i]未定义)的树的元素的数量.所以它应该被初始化为1,而不是我.最初,每个元素是大小为1的单独的“单身”树.