聯盟查找脫節+路徑壓縮算法

我在考試這個星期天，我只是想確認一下，如果我在做什麼是正確的（你知道考試使我懷疑）聯盟查找脫節+路徑壓縮算法

這是怎樣的算法工作：

int Find(int x) 
{ // Return the set containing x and compress the path from x to root 
    // First, find the root 
int z = x; while (P[z] > 0) { z = P[z]; } int root = z; 
// Start at x again and reset the parent // of every node on the path from x to root z = x; 
while (P[z] > 0) 
{ int t = P[z]; 
    P[z] = root; // Reset Parent of z to root 
z = t; } 
return root; }

這是一個問題：

回憶從一組n個元素的不相交集開發的算法聯盟查找問題。查找使用路徑壓縮和Union 使用排名。另外，同一級別的兩棵樹的聯盟選擇與第二個參數相關的根作爲新根。從一組S = {1,2，...，10}和10個不相交的子集開始，每個子集包含單個元素。一個。執行後繪製最後一組樹：
聯盟（1,2），聯盟（3,4），聯盟（5,6），聯盟（1,5），聯盟（1,3）。

這是我的解決問題的辦法：

enter image description here

我很想對本算法任何提示或建議。

謝謝！

來源

2014-06-26 Sobiaholic

你的第三步是錯誤的。 1應該指向6而不是2.另外，每個根應該有一個等級。 – tmyklebu

無關緊要的是，與記憶算法和在紙上運行算法相比，你的年輕人有更好的事情要做。相比之下，通過對路徑壓縮進行聯合分析的分析是一個更好的事情。 – tmyklebu

你的意思是第四步？我在哪裏工會（1,5）？但具有路徑壓縮的find（1）發生在集合{1,2}上。 – Sobiaholic

的Union-Find Set查找操作的關鍵點是路徑壓縮。

如果我們知道集合A的根是r1，並且集合B的根是r2，那麼當將集合A和集合B連接在一起時。最簡單的辦法就是讓集B的根作爲集合A的根，這意味着father[r2] = r1;

但它不是那麼「聰明」，當r2的兒子，我們說x，想知道它的根，x要求其父親r2，然後父親r2問自己的父親r1，blabla，直到根r1。當再次詢問x的根時，x詢問其父親r1「什麼是我們的根？」，r1沒有必要再次重複上一個循環。由於r1已經知道其根目錄是r2,r1可以直接返回到x。

簡言之，x的根也x的父親的根。所以我們得到如何實現路徑壓縮（我認爲遞歸是更簡單）：

int Find(int x) 
{ 
    // initial each element's root as itself, which means father[x] = x; 
    // if an element finds its father is itself, means root is found 
    if(x == father[x]) 
     return father[x]; 
    int temp = father[x]; 
    // root of x's father is same with root of x's father's root 
    father[x] = Find(temp); 
    return father[x]; 
}

這是非常高的性能，關於時間的路徑compressioned查找操作的複雜性，請參閱：http://www.gabrielnivasch.org/fun/inverse-ackermann

來源

2015-02-09 13:32:54 coderz

聯盟查找脫節+路徑壓縮算法

回答

相關問題