java - 按大小联合无限循环

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;
}