英文:
Union Find in Java
问题
我正在尝试实现并查集算法。基本上，我在算法中遇到困难的部分是并集操作。应该发生的情况是，有一个数字列表（起初所有数字都是列表中的索引），如果两个数字恰好相同，则意味着它们是连接的。当发生并集操作时，比如说 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 相当新手，所以我猜这可能是因为我之前没有接触过。非常感谢任何帮助。
英文:
I am trying to implement the union-find algorithm. Basically the part of the algorithm that I am struggling with is the union part. What is supposed to happen is that there is a list of numbers (starts off with all of them being their index in the list) and if two numbers happen to have the same value then it means that they are connected. When the union happens like say Union(1,6) then the list would go from [0,1,2,3,4,5,6,7,8] to [0,6,2,3,4,5,6,7,8] (assuming the array was size 9 to start). My way of implementing this is shown here:
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==id[q];
}
public void Union(int p, int q) {
for (int i=0; i < id.length; i++) {
if (id[i] == id
) {
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();
}
}
However, the professor while going over this said that this was not right and that the union function should instead look like this:
public void Union(int p, int q) {
int pid = id;
int qid = id[q];
for (int i=0; i < id.length; i++) {
if (id[i] == pid) {
id[i] = qid;
}
}
}
Both versions work and will change id so that it is [0,6,2,3,4,5,6,7,8] like it should be which makes me think that there's something under the hood that makes the way I did it wrong but I don't even know where to begin on what that could be. I'm fairly new to Java so I'm guessing it I just haven't been exposed to it before. Any help would be greatly appreciated.
答案1
得分: 3
你的算法在逻辑上是错误的，因为它在循环过程中更改了 id 的值，因此未能更新在索引 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]
英文:
Your algorithm is logically incorrect, because it changes the value of id in the middle of the loop, and therefore fails to update occurrences which occur after index p. Consider this example:
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));
Output:
[4, 1, 1, 4, 4]
The correct output would be:
[4, 4, 4, 4, 4]
通过集体智慧和协作来改善编程学习和解决问题的方式。致力于成为全球开发者共同参与的知识库，让每个人都能够通过互相帮助和分享经验来进步。
评论