带路径压缩算法的加权Quick-Union
有一个“加权快速联合路径压缩”算法。
代码：
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]]意味着我们只到达节点的第二个ancester，而不是root。 -
iz[]包含从0到N-1整数。iz[]如何帮助我们知道集合中元素的数量？
有人可以为我澄清一下吗？
首先要明白id是一个森林 。 id[i]是id[i]的父母。 如果id[i] == i则表示i是根。
对于某些root i （其中id[i] == i ），则iz[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; }
路径压缩如何工作？
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]是以iz[i]为根的树的元素数（或者如果i不是根，则iz[i]未定义）。 所以它应该被初始化为1 ，而不是i 。 最初，每个元素都是大小为1的单独“单例”树。
id [i] = id [id [i]]; //此行代表“路径压缩”
上面的代码是“简单的一次通过变量”，如Union Find（Algorithms，第一部分，Kevin Wayne和Robert Sedgewick）的幻灯片中所提到的。 因此，您对问题1的猜测是正确的。 每个被检查的节点都指向其祖父母。
要使每个被检查的节点指向根，我们将需要两遍实现：
/** * Returns the component identifier for the component containing site p. * @param p the integer representing one site * @return the component identifier for the component containing site p * @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
问题1.说id [i] = id [id [i]]行是不对的; 只会到达root的第二个祖先。你会意识到while 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.在union函数中，您意识到我们有行iz [j] + = iz [i]; 和iz [i] + = iz [j]; 它将根节点的大小更新为连接在一起的两个组件的大小的总和。 这有效地更新了节点大小。
还有一点需要注意：
在我们制作id[i]=id[id[i]]时找到根; 让我成为其盛大的父母
– 然后id[i]的大小将减小ii，e的大小; iz[id[i]]-=iz[i]
现在这使代码完全正确。
我不确定这一点，但直觉上我觉得，它的缺席不会引起问题，因为我们总是比较根的大小。