按大小联合无限循环

Question

我正在努力从头开始实现 Union-Find 数据结构，但我遇到了一个问题，如果尝试重复 union 调用，我的 find 方法会出现无限循环。

我正在实施按大小联合，并使用路径压缩 进行查找。我创建了一个只有 10 个元素（0 到 N-1）的测试实现

示例：

U 3 1  //Union 1 -> 3
U 0 2  //Union 2 -> 0
U 0 2  //Union 2 -> 0 , infinite loop results
U 1 4  //Union 4 -> 1 , results in infinite loop

当我执行第二个 U 0 2 时，循环被捕获，因为索引 2 处的值为零，根也为零，因此循环重复循环。当我尝试执行 U 1 4 时，遵循相同的逻辑。我在 find 中的第二个循环逻辑不正确。

我的问题是：我该如何处理这些案例，以免陷入这个无限循环？

这是我的查找方法：

/*
 * Search for element 'num' and returns the key in the root of tree
 * containing 'num'. Implements path compression on each find. 
 */
public int find (int num) {
    totalPathLength++;
    int k = num;
    int root = 0;
    // Find the root
    while (sets[k] >= 0) {
        k = sets[k];
        totalPathLength++;
    }
    root = k;
    k = num;

    // Point all nodes along path to root
    /* INFINITE LOOP OCCURS HERE */
    while (sets[k] >= 0) {
        sets[k] = root;
    }
    return root;
}

我如何调用与 union 相关的 find：（位于 main 中）

   int x = Integer.parseInt(tokens[1]);
   int y = Integer.parseInt(tokens[2]);
   // Call to find upon the 2nd: U 0 2, results in inf. loop
   if (uf.find(x) == x && uf.find(y) == y) {
        uf.union(x, y);
   }

Answer 1

你没有遍历第二个循环中的路径。这意味着您要么 num 是根，要么您的方法进入无限循环。像这样更改循环：

while (sets[k] >= 0) {
    // save old parent to variable
    int next = sets[k];

    sets[k] = root;
    k = next;
}

按大小联合无限循环

Union By Size Infinite Loop

java

loops

data-structures

union-find