联合查找 Java

Question

我正在尝试实现联合查找算法。基本上，我正在努力解决的算法部分是并集部分。应该发生的是有一个数字列表（开始时所有数字都是它们在列表中的索引）并且如果两个数字恰好具有相同的值那么这意味着它们是连接的。当 union 像 Union(1,6) 这样发生时，列表将从 [0,1,2,3,4,5,6,7,8] 到 [0,6,2,3,4,5 ,6,7,8]（假设数组大小为 9）。我的实现方式如下所示：

public class QuickFindUF {
    private int[] id;
    
    public QuickFindUF(int N) {
        id = new int[N];
        for (int i=0; i < N; i++) {
            id[i] = i;
        }       
    }
    
    public boolean connected(int p, int q) {
        return id[p]==id[q];
    }
    
    public void Union(int p, int q) {
        for (int i=0; i < id.length; i++) {
            if (id[i] == id[p]) {
                id[i] = id[q];
            }
        }
    }
    public void printID() {
        for (int i = 0; i < id.length; i++) {
            System.out.print(id[i]);
        }
    }
    
    
    public static void main(String[] args) {
        QuickFindUF quickfind = new QuickFindUF(9);
        quickfind.printID();
        System.out.println();
        quickfind.Union(1,6);
        quickfind.printID();
        
        
    }
}

然而，教授在复习时说这是不对的，联合函数应该如下所示：

public void Union(int p, int q) {
        int pid = id[p];
        int qid = id[q];
        for (int i=0; i < id.length; i++) {
            if (id[i] == pid) {
                id[i] = qid;
            }
        }
    }

两个版本都可以工作，并且会更改 id，使其成为 [0,6,2,3,4,5,6,7,8] 应该的样子，这让我觉得幕后有些东西使我做错的方式，但我什至不知道从哪里开始可能是什么。我是 Java 的新手，所以我猜我只是之前没有接触过它。任何帮助将不胜感激。

Answer 1

您的算法在逻辑上是不正确的，因为它在循环中间更改了 id[p] 的值，因此无法更新索引 p 之后出现的事件。考虑这个例子：

int[] id = { 1, 1, 1, 4, 4 };
int p = 0, q = 3;

for(int i = 0; i < id.length; i++) {
    if(id[i] == id[p]) {
        id[i] = id[q];
    }
}

System.out.println(Arrays.toString(id));

输出：

[4, 1, 1, 4, 4]

正确的输出是：

[4, 4, 4, 4, 4]

联合查找 Java

Union Find in Java

java

union-find