具有路徑壓縮算法的加權快速聯合

代碼：

public class WeightedQU 
{ 
    private int[] id; 
    private int[] iz; 

    public WeightedQU(int N) 
    { 
     id = new int[N]; 
     iz = new int[N]; 
     for(int i = 0; i < id.length; i++) 
     { 
      iz[i] = i; 
      id[i] = i; 
     } 
    } 

    public int root(int i) 
    { 
     while(i != id[i]) 
     { 
      id[i] = id[id[i]]; // this line represents "path compression" 
      i = id[i]; 
     } 
     return i; 
    } 

    public boolean connected(int p, int q) 
    { 
     return root(p) == root(q); 
    } 

    public void union(int p, int q) // here iz[] is used to "weighting" 
    { 
     int i = root(p); 
     int j = root(q); 
     if(iz[i] < iz[j]) 
     { 
      id[i] = j; 
      iz[j] += iz[i]; 
     } 
     else 
     { 
      id[j] = i; 
      iz[i] += iz[j]; 
     } 
    } 
}

問題：

怎樣的路徑壓縮工作？ id[i] = id[id[i]]意味着我們只到達節點的第二個祖先，而不是根。
iz[]包含從0到N-1的整數。 iz[]如何幫助我們知道集合中元素的數量？

有人可以爲我澄清這一點嗎？

來源

2012-10-02 Aleksei Chepovoi

閱讀c/C++中的算法，第1-4部分，robert sedgewick，第1章，很好的解釋。 – rendon

首先明白id是森林。 id[i]是i的母公司。如果id[i] == i這意味着i是一個根。

對於一些根i（其中id[i] == i）然後iz[i]處於樹在i根元素的數量。

public int root(int i) 
{ 
    while(i != id[i]) 
    { 
     id[i] = id[id[i]]; // this line represents "path compression" 
     i = id[i]; 
    } 
    return i; 
}

怎樣的路徑壓縮工作？ id[i] = id[id[i]]意味着我們只到達節點的第二個祖先，而不是根。

因爲我們正在升樹尋找根，所以我們將節點從父母移到他們的祖父母。這使樹部分變平。請注意，此操作不會更改節點所屬的樹，這是我們感興趣的全部內容。這是路徑壓縮技術。

（你也注意到循環嗎？while(i == id[i])終止一旦i是根節點）

iz[]包含整數從0到N-1。 iz[]如何幫助我們知道集合中元素的數量？

有一個在代碼中的抄寫錯誤：

這是正確的版本：

for(int i = 0; i < id.length; i++) 
{ 
    iz[i] = 1; // RIGHT 
    id[i] = i; 
}

iz[i]是在i根的樹元素的數量（或者，如果i不是根，那麼iz[i]是未定義的）。所以它應該初始化爲1，而不是i。最初，每個元素是一個大小爲1的單獨「單獨」樹。

來源

2012-10-02 19:29:09

關於路徑壓縮，這是路徑壓縮的單程變體，使路徑中的每個其他節點指向其祖父（將路徑長度減半）。而Two-pass更像是將第二個循環添加到root將每個檢查節點的id []設置爲根。似乎有關補充。 – RBz

問題1。說行ID [i] = id [id [i]]是不對的;只有到達根的第二個祖先。你會意識到，while循環while（i！= id [i]）只在節點i指向根時纔會停止，即當i == id [i]。這時候我們應使用行id [i] = id [id [i]]將節點指向根;內部id [i]是根。

問題2：

初始化iz [i] = i;實際上它應該是iz [i] = 1;意思是，每個節點的大小在初始時都是由1開始的，因爲它們的大小爲1. 在聯合函數中，你意識到我們有行iz [j] + = iz [i];和iz [i] + = iz [j];它將根節點的大小更新爲連接在一起的兩個組件大小的總和。這有效地更新節點大小。

來源

2013-03-27 10:13:16

id [i] = id [id [i]]; //此行代表「路徑壓縮」

上面的代碼是「簡單的單遍變體」，如聯合查找幻燈片（算法，第一部分由Kevin Wayne和Robert Sedgewick）中提到的。因此，你對問題1的猜測是正確的。每個檢查節點都指向它的祖父母。

爲了使各被檢節點指向我們將需要兩個通實現根：

/** 
* Returns the component identifier for the component containing site <tt>p</tt>. 
* @param p the integer representing one site 
* @return the component identifier for the component containing site <tt>p</tt> 
* @throws java.lang.IndexOutOfBoundsException unless 0 <= p < N 
*/ 
public int find(int p) { 
    int root = p; 
    while (root != id[root]) 
     root = id[root]; 
    while (p != root) { 
     int newp = id[p]; 
     id[p] = root; 
     p = newp; 
    } 
    return root; 
}

參考： http://algs4.cs.princeton.edu/15uf/WeightedQuickUnionPathCompressionUF.java.html

來源

2014-10-23 20:29:54 DML

一兩件事這裏要注意：

雖然發現當我們正在製作id[i]=id[id[i]]即：使我在其祖父

- 然後id[i]的大小將減少我i，e的大小; iz[id[i]]-=iz[i]

現在，這使得代碼完全正確。

我不知道這個，但直覺上我覺得，它的缺席並不會造成問題，因爲我們總是比較根的大小。

來源

2017-05-26 07:45:51

具有路徑壓縮算法的加權快速聯合

回答

相關問題