聯合按大小無限循環

我正在從頭開始實施聯合查找數據結構，並遇到一個問題，如果嘗試重複聯合調用，無限循環會導致我的查找方法。聯合按大小無限循環

我正在實施聯合按大小，找到使用路徑壓縮。我已經創建了一個測試實施只有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時，遵循相同的邏輯。我在查找的第二個循環有不正確的邏輯。

我的問題是：我該如何處理這些案例，以免陷入這種無限循環？

這是我的查找方法：

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

如何我打電話找關係到工會：（位於主）

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

來源

2015-04-01 Evan Bechtol

你不經過的路徑在第二個循環中。這意味着你或者num是一個根，或者你的方法進入無限循環。像這樣改變你的循環：

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

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

來源

2015-04-01 17:30:37 fabian

謝謝fabian，解決了我的問題！我不能相信我錯過了這麼小的東西！：P – 2015-04-01 18:02:33

聯合按大小無限循環

回答

相關問題