java 带路径压缩算法的加权 Quick-Union
声明：本页面是StackOverFlow热门问题的中英对照翻译，遵循CC BY-SA 4.0协议，如果您需要使用它，必须同样遵循CC BY-SA许可，注明原文地址和作者信息，同时你必须将它归于原作者（不是我）：StackOverFlow
原文地址: http://stackoverflow.com/questions/12696803/
Warning: these are provided under cc-by-sa 4.0 license. You are free to use/share it, But you must attribute it to the original authors (not me):
StackOverFlow
Weighted Quick-Union with Path Compression algorithm
提问by Aleksei Chepovoi
There is a "Weighted Quick-Union with Path Compression" algorithm.
有一个“带路径压缩的加权快速联合”算法。
The code:
代码：
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];
}
}
}
Questions:
问题：
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.iz[]contains integers from0toN-1. How doesiz[]help us know the number of elements in the set?
路径压缩如何工作？
id[i] = id[id[i]]意味着我们只到达节点的第二个祖先，而不是根。iz[]包含从0到的整数N-1。如何iz[]帮助我们知道集合中元素的数量？
Can someone clarify this for me?
有人可以为我澄清这一点吗？
回答by Andrew Tomazos
First understand that idis a forest. id[i]is the parent of i. If id[i] == iit means that iis a root.
首先明白id是一片森林。id[i]是 的父级i。如果id[i] == i它意味着这i是一个根。
For some root i(where id[i] == i) then iz[i]is the number of elements in the treerooted at 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.
路径压缩如何工作？
id[i] = id[id[i]]意味着我们只到达节点的第二个祖先，而不是根。
As we are ascending the tree to find the root we move nodes from their parents to their grandparents. This partially flattens the tree. Notice that this operation doesn't change which tree the node is a member of, this is all we are interested in. This is the path compression technique.
当我们向上树寻找根时，我们将节点从它们的父节点移动到它们的祖父节点。这部分地压平了树。请注意，此操作不会更改节点所属的树，这就是我们感兴趣的全部内容。这就是路径压缩技术。
(You did notice the loop right? while(i == id[i])terminates once iis a root node)
（你注意到循环了吗？ while(i == id[i])终止一次i是根节点）
iz[]contains integers from0toN-1. How doesiz[]help us know the number of elements in the set?
iz[]包含从0到的整数N-1。如何iz[]帮助我们知道集合中元素的数量？
There is a transcription error in the code:
代码中有一个转录错误：
for(int i = 0; i < id.length; i++)
{
iz[i] = i; // WRONG
id[i] = i;
}
This is the correct version:
这是正确的版本：
for(int i = 0; i < id.length; i++)
{
iz[i] = 1; // RIGHT
id[i] = i;
}
iz[i]is the number of elements for a tree rooted at i(or if iis not a root then iz[i]is undefined). So it should be initialized to 1, not i. Initially each element is a seperate "singleton" tree of size 1.
iz[i]是根植于i（或者如果i不是根则iz[i]未定义）的树的元素数。所以它应该被初始化为1，而不是i。最初，每个元素都是大小为 的单独“单例”树1。
回答by DML
id[i] = id[id[i]]; // this line represents "path compression"
id[i] = id[id[i]]; // 这一行代表“路径压缩”
The above code is "Simpler one-pass variant" as mentioned in the slide of Union Find (Algorithms, Part I by Kevin Wayne and Robert Sedgewick). Therefore your guess for question 1 is correct. Each examined node points to its grandparent.
上面的代码是 Union Find（算法，第一部分，Kevin Wayne 和 Robert Sedgewick）幻灯片中提到的“更简单的单遍变体”。因此，您对问题 1 的猜测是正确的。每个检查的节点都指向它的祖父节点。
To make each examined node points to the root we will need two-pass implementation:
为了使每个检查的节点指向根，我们需要两遍实现：
/**
* 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;
}
Reference: http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionPathCompressionUF.java.html
参考：http: //algs4.cs.princeton.edu/15uf/WeightedQuickUnionPathCompressionUF.java.html
回答by Gaurav jhamnani
One more thing to be noted here:
这里还要注意一件事：
While finding the root when we are making id[i]=id[id[i]]i.e; making i under its grand parent
在我们制作id[i]=id[id[i]]ie的时候找根；让我在它的祖父母之下
-then size of id[i]will decrease by size of i i,e; iz[id[i]]-=iz[i]
- 那么 的大小id[i]将减少 ii,e 的大小；iz[id[i]]-=iz[i]
Now this makes code perfectly correct.
现在这使得代码完全正确。
I am not sure about this but intuitively i feel, Its absence does not cause problems because we are always comparing size of the roots.
我不确定这一点，但直觉上我觉得，它的缺失不会引起问题，因为我们总是在比较根的大小。
回答by Paul Odero
Question 1. It is not right to say that the line id[i] = id[id[i]]; only reaches the second ancestor of the root.You will realize that while loop while(i != id[i]) stops only when the node i is pointing at the root i.e when i == id[i].By this time we shall have pointed the node to the root using the line id[i] = id[id[i]]; where the inner id[i] is the root.
问题1. id[i] = id[id[i]]; 行是不对的 只到达根的第二个祖先。你会意识到 while 循环 while(i != id[i]) 只有当节点 i 指向根时才停止，即当 i == id[i] 时。此时我们应该使用 id[i] = id[id[i]] 行将节点指向根节点；其中内部 id[i] 是根。
Question 2.
问题2。
You are wrong to initialize iz[i] = i; actually it should be iz[i] = 1; meaning, each and every node size is initialized by 1 at the beginning since they are of size 1. In the union function you realize that we have the lines iz[j] += iz[i]; and iz[i] += iz[j]; which updates the size of the root node to be the sum of the sizes of the two components joined together. This efficiently updates the nodes sizes.
你是错误的初始化 iz[i] = i; 实际上应该是 iz[i] = 1; 这意味着，每个节点的大小在开始时都被初始化为 1，因为它们的大小为 1。在联合函数中，您会意识到我们有 iz[j] += iz[i]; 和 iz[i] += iz[j]; 它将根节点的大小更新为连接在一起的两个组件的大小之和。这有效地更新了节点大小。
