java - 快速联合 Java 实现

Question

我一直在研究快速联合算法。下面的代码是实现的示例。有人可以向我解释一下 root 方法 中发生了什么吗？

public class quickUnion {
    private int[] id;

    public void QuickUnionUF(int N){
        id = new int [N];
        for(int i = 0; i < N; i++){
            id[i] = i;
        }
    }

    private int root(int i){
        while (i != id[i]){
            i = id[i];
        }
        return i;
    }
    public boolean connected(int p, int q){
        return root(p) == root(q);
    }
    public void union(int p, int q){
        int i = root(p);
        int j = root(q);
        id[i] = j;
    }
}

Answer 1

union find 的核心原则是每个元素都属于一个不相交的元素集合。这意味着，如果您绘制一个森林(一组树)，该森林将包含所有元素，并且没有元素位于两棵不同的树中。

在构建这些树时，您可以想象任何节点都有一个父节点或者是根节点。在 union find 的这个实现中(以及大多数 union find 实现)，每个元素的父元素都存储在数组中该元素的索引处。因此，等价于 id[i] 的元素是 i 的父元素。

你可能会问:如果我没有 parent (也就是根)怎么办？在这种情况下，约定是将 i 设置为它自己(i 是它自己的父级)。因此，id[i] == i 只是检查我们是否到达了树的根。

将所有这些放在一起，root 函数从起始节点开始遍历树(逐个父节点)，直到到达根节点。然后它返回根。

顺便说一句:为了让这个算法更快地到达根，一般的实现会“扁平化”树:到达根所需的父节点越少，根函数返回的速度就越快。因此，在许多实现中，您会看到一个额外的步骤，您将元素的父元素设置为其原始祖父元素 (id[i] = id[id[i]])。