我在考試這個星期天,我只是想確認一下,如果我在做什麼是正確的(你知道考試使我懷疑)聯盟查找脫節+路徑壓縮算法
這是怎樣的算法工作:
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)。
這是我的解決問題的辦法:
我很想對本算法任何提示或建議。
謝謝!
你的第三步是錯誤的。 1應該指向6而不是2.另外,每個根應該有一個等級。 – tmyklebu
無關緊要的是,與記憶算法和在紙上運行算法相比,你的年輕人有更好的事情要做。相比之下,通過對路徑壓縮進行聯合分析的分析是一個更好的事情。 – tmyklebu
你的意思是第四步?我在哪裏工會(1,5)?但具有路徑壓縮的find(1)發生在集合{1,2}上。 – Sobiaholic