1

我正在从头开始实现一个 Union-Find 数据结构，并且遇到一个问题，如果尝试重复联合调用，我的 find 方法会导致无限循环。

我正在实现Union By Size，并使用路径压缩进行查找。我创建了一个只有 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;
}

我如何称呼与联合相关的 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);
   }
4

1 回答 1

1

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

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

    sets[k] = root;
    k = next;
}
于 2015-04-01T17:30:37.200 回答