java - 为什么在普林斯顿的这个加权快速联合实施中使用“while”

Question

作为我“回归基础”之旅的一部分，我正在研究这种方法，我要么遗漏了一些非常明显的东西，要么while这里不需要操作员：

// Return component identifier for component containing p
public int find(int p) {
    while (p != id[p])
        p = id[p];
    return p;
}

完整的来源在这里。

看起来它可以像这样简单（而且整个函数相当没有意义）：

public int find(int p) {
    return id[p];
}

score 3 · Accepted Answer

实际上不是。

它将从一个指针到另一个指针遍历数组，直到指针等于元素 id。

例子：

id = [ 2 0 3 3 ]

然后，find(1)会做类似的事情：

id[1] = 0 != 1
id[0] = 2 != 0
id[2] = 3 != 2
id[3] = 3 == 3 => return 3

score 2 · Accepted Answer

给定// id[i] = parent of i，这个循环找到最顶层的祖先，它被认为是组件标识符。否则，plainid[p]是的父级p，并且您的陈述仅在p作为所述最顶层的祖先时才是正确的。

score 0 · Accepted Answer

私人 int[] 标识；// id[i] = i 的父级

那是描述的顶部，所以 id[p] 与 while 循环不同

3 回答 3