java - 加权联合查找算法

Question

我是 Java 的新手，我有一个加权联合查找算法。当我在 eclipse 中的剪贴簿页面上运行这段代码时，它会一直计算下去。

java代码

public class weightedUF {
    private int[] id;
    private int[] sz;

    public weightedUF(int N) {
        id = new int[N];
        sz = new int[N];
        for (int i = 0; i < N; i++) {
            id[i] = i;
        }
        for (int i = 0; i < N; i++) {
            sz[i] = 1;
        }
    }

    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);
        if (sz[i] < sz[j]) {
            id[i] = j;
            sz[j] += sz[i];
        }
        else {
            id[j] = i;
            sz[i] += sz[j];
        }
        id[i] = j;
    }
}

剪贴簿测试代码

weightedUF union = new weightedUF(10);
union.union(9, 2);
union.union(5, 2);
union.union(1, 8);
union.union(5, 7);
union.union(4, 3);
union.union(0, 7);
union.union(1, 3);
union.union(2, 4);
union.union(8, 6);
union

Answer 1

我认为你应该删除最后一行:

 id[i] = j;

它正在破坏您的 id 数组。