并查集(Union-Find)算法介紹

StepanieGue 8年前發布 | 29K 次閱讀算法并查集

本文主要介紹解決動態連通性一類問題的一種算法，使用到了一種叫做并查集的數據結構，稱為 Union-Find 。

更多的信息可以參考 Algorithms 一書的 Section 1.5 ，實際上本文也就是基于它的一篇讀后感吧。原文中更多的是給出一些結論，我嘗試給出一些思路上的過程，即為什么要使用這個方法，而不是別的什么方法。我覺得這個可能更加有意義一些，相比于記下一些結論。

關于動態連通性

我們看一張圖來了解一下什么是動態連通性：

假設我們輸入了一組整數對，即上圖中的 (4, 3) (3, 8) 等等，每對整數代表這兩個 points/sites 是連通的。那么隨著數據的不斷輸入，整個圖的連通性也會發生變化，從上圖中可以很清晰的發現這一點。同時，對于已經處于連通狀態的 points/sites ，直接忽略，比如上圖中的 (8, 9) 。

動態連通性的應用場景：

網絡連接判斷：

如果每個 pair 中的兩個整數分別代表一個網絡節點，那么該 pair 就是用來表示這兩個節點是需要連通的。那么為所有的 pairs 建立了動態連通圖后，就能夠盡可能少的減少布線的需要，因為已經連通的兩個節點會被直接忽略掉。

變量名等同性 ( 類似于指針的概念 ) ：

在程序中，可以聲明多個引用來指向同一對象，這個時候就可以通過為程序中聲明的引用和實際對象建立動態連通圖來判斷哪些引用實際上是指向同一對象。

對問題建模：

在對問題進行建模的時候，我們應該盡量想清楚需要解決的問題是什么。因為模型中選擇的數據結構和算法顯然會根據問題的不同而不同，就動態連通性這個場景而言，我們需要解決的問題可能是：

給出兩個節點，判斷它們是否連通，如果連通，不需要給出具體的路徑
給出兩個節點，判斷它們是否連通，如果連通，需要給出具體的路徑

就上面兩種問題而言，雖然只有是否能夠給出具體路徑的區別，但是這個區別導致了選擇算法的不同，本文主要介紹的是第一種情況，即不需要給出具體路徑的 Union-Find 算法，而第二種情況可以使用基于 DFS 的算法。

建模思路：

最簡單而直觀的假設是，對于連通的所有節點，我們可以認為它們屬于一個組，因此不連通的節點必然就屬于不同的組。隨著 Pair 的輸入，我們需要首先判斷輸入的兩個節點是否連通。如何判斷呢？按照上面的假設，我們可以通過判斷它們屬于的組，然后看看這兩個組是否相同，如果相同，那么這兩個節點連通，反之不連通。為簡單起見，我們將所有的節點以整數表示，即對 N 個節點使用 0 到 N-1 的整數表示。而在處理輸入的 Pair 之前，每個節點必然都是孤立的，即他們分屬于不同的組，可以使用數組來表示這一層關系，數組的 index 是節點的整數表示，而相應的值就是該節點的組號了。該數組可以初始化為：

for(int i = 0; i < size; i++)  
    id[i] = i;

即對于節點 i ，它的組號也是 i 。

初始化完畢之后，對該動態連通圖有幾種可能的操作：

查詢節點屬于的組

數組對應位置的值即為組號

判斷兩個節點是否屬于同一個組

分別得到兩個節點的組號，然后判斷組號是否相等

連接兩個節點，使之屬于同一個組

分別得到兩個節點的組號，組號相同時操作結束，不同時，將其中的一個節點的組號換成另一個節點的組號

獲取組的數目

初始化為節點的數目，然后每次成功連接兩個節點之后，遞減 1

API

我們可以設計相應的 API ：

注意其中使用整數來表示節點，如果需要使用其他的數據類型表示節點，比如使用字符串，那么可以用哈希表來進行映射，即將 String 映射成這里需要的 Integer 類型。

分析以上的 API ，方法 connected 和 union 都依賴于 find ， connected 對兩個參數調用兩次 find 方法，而 union 在真正執行 union 之前也需要判斷是否連通，這又是兩次調用 find 方法。因此我們需要把 find 方法的實現設計的盡可能的高效。所以就有了下面的 Quick-Find 實現。

Quick-Find 算法：

public class UF  
{  
    private int[] id; // access to component id (site indexed)  
    private int count; // number of components  
    public UF(int N)  
    {  
        // Initialize component id array.  
        count = N;  
        id = new int[N];  
        for (int i = 0; i < N; i++)  
            id[i] = i;  
    }  
    public int count()  
    { return count; }  
    public boolean connected(int p, int q)  
    { return find(p) == find(q); }  
    public int find(int p)  
    { return id[p]; }  
    public void union(int p, int q)  
    {  
        // 獲得p和q的組號  
        int pID = find(p);  
        int qID = find(q);  
        // 如果兩個組號相等，直接返回  
        if (pID == qID) return;  
        // 遍歷一次，改變組號使他們屬于一個組  
        for (int i = 0; i < id.length; i++)  
            if (id[i] == pID) id[i] = qID;  
        count--;  
    }  
}

舉個例子，比如輸入的 Pair 是 (5 ， 9) ，那么首先通過 find 方法發現它們的組號并不相同，然后在 union 的時候通過一次遍歷，將組號 1 都改成 8 。當然，由 8 改成 1 也是可以的，保證操作時都使用一種規則就行。

上述代碼的 find 方法十分高效，因為僅僅需要一次數組讀取操作就能夠找到該節點的組號，但是問題隨之而來，對于需要添加新路徑的情況，就涉及到對于組號的修改，因為并不能確定哪些節點的組號需要被修改，因此就必須對整個數組進行遍歷，找到需要修改的節點，逐一修改，這一下每次添加新路徑帶來的復雜度就是線性關系了，如果要添加的新路徑的數量是 M ，節點數量是 N ，那么最后的時間復雜度就是 MN ，顯然是一個平方階的復雜度，對于大規模的數據而言，平方階的算法是存在問題的，這種情況下，每次添加新路徑就是“牽一發而動全身”，想要解決這個問題，關鍵就是要提高 union 方法的效率，讓它不再需要遍歷整個數組。

Quick-Union 算法：

考慮一下，為什么以上的解法會造成“牽一發而動全身”？因為每個節點所屬的組號都是單獨記錄，各自為政的，沒有將它們以更好的方式組織起來，當涉及到修改的時候，除了逐一通知、修改，別無他法。所以現在的問題就變成了，如何將節點以更好的方式組織起來，組織的方式有很多種，但是最直觀的還是將組號相同的節點組織在一起，想想所學的數據結構，什么樣子的數據結構能夠將一些節點給組織起來？常見的就是鏈表，圖，樹，什么的了。但是哪種結構對于查找和修改的效率最高？毫無疑問是樹，因此考慮如何將節點和組的關系以樹的形式表現出來。

如果不改變底層數據結構，即不改變使用數組的表示方法的話。可以采用 parent-link 的方式將節點組織起來，舉例而言， id[p] 的值就是 p 節點的父節點的序號，如果 p 是樹根的話， id[p] 的值就是 p ，因此最后經過若干次查找，一個節點總是能夠找到它的根節點，即滿足 id[root] = root 的節點也就是組的根節點了，然后就可以使用根節點的序號來表示組號。所以在處理一個 pair 的時候，將首先找到 pair 中每一個節點的組號 ( 即它們所在樹的根節點的序號 ) ，如果屬于不同的組的話，就將其中一個根節點的父節點設置為另外一個根節點，相當于將一顆獨立的樹編程另一顆獨立的樹的子樹。直觀的過程如下圖所示。但是這個時候又引入了問題。

在實現上，和之前的 Quick-Find 只有 find 和 union 兩個方法有所不同：

private int find(int p)  
{  
    // 尋找p節點所在組的根節點，根節點具有性質id[root] = root  
    while (p != id[p]) p = id[p];  
    return p;  
}  
public void union(int p, int q)  
{  
    // Give p and q the same root.  
    int pRoot = find(p);  
    int qRoot = find(q);  
    if (pRoot == qRoot)  
        return;  
    id[pRoot] = qRoot;    // 將一顆樹(即一個組)變成另外一課樹(即一個組)的子樹  
    count--;  
}

樹這種數據結構容易出現極端情況，因為在建樹的過程中，樹的最終形態嚴重依賴于輸入數據本身的性質，比如數據是否排序，是否隨機分布等等。比如在輸入數據是有序的情況下，構造的 BST 會退化成一個鏈表。在我們這個問題中，也是會出現的極端情況的，如下圖所示。

為了克服這個問題， BST 可以演變成為紅黑樹或者 AVL 樹等等。

然而，在我們考慮的這個應用場景中，每對節點之間是不具備可比性的。因此需要想其它的辦法。在沒有什么思路的時候，多看看相應的代碼可能會有一些啟發，考慮一下 Quick-Union 算法中的 union 方法實現：

public void union(int p, int q)  
{  
    // Give p and q the same root.  
    int pRoot = find(p);  
    int qRoot = find(q);  
    if (pRoot == qRoot)  
        return;  
    id[pRoot] = qRoot;  // 將一顆樹(即一個組)變成另外一課樹(即一個組)的子樹  
    count--;  
}

上面 id[pRoot] = qRoot 這行代碼看上去似乎不太對勁。因為這也屬于一種“硬編碼”，這樣實現是基于一個約定，即 p 所在的樹總是會被作為 q 所在樹的子樹，從而實現兩顆獨立的樹的融合。那么這樣的約定是不是總是合理的呢？顯然不是，比如 p 所在的樹的規模比 q 所在的樹的規模大的多時， p 和 q 結合之后形成的樹就是十分不和諧的一頭輕一頭重的”畸形樹“了。

所以我們應該考慮樹的大小，然后再來決定到底是調用：

id[pRoot] = qRoot 或者是 id[qRoot] = pRoot

即總是 size 小的樹作為子樹和 size 大的樹進行合并。這樣就能夠盡量的保持整棵樹的平衡。

所以現在的問題就變成了：樹的大小該如何確定？

我們回到最初的情形，即每個節點最一開始都是屬于一個獨立的組，通過下面的代碼進行初始化：

for (int i = 0; i < N; i++)  
    id[i] = i;    // 每個節點的組號就是該節點的序號

以此類推，在初始情況下，每個組的大小都是 1 ，因為只含有一個節點，所以我們可以使用額外的一個數組來維護每個組的大小，對該數組的初始化也很直觀：

for (int i = 0; i < N; i++)  
    sz[i] = 1;    // 初始情況下，每個組的大小都是1

而在進行合并的時候，會首先判斷待合并的兩棵樹的大小，然后按照上面圖中的思想進行合并，實現代碼：

public void union(int p, int q)  
{  
    int i = find(p);  
    int j = find(q);  
    if (i == j) return;  
    // 將小樹作為大樹的子樹  
    if (sz[i] < sz[j]) { id[i] = j; sz[j] += sz[i]; }  
    else { id[j] = i; sz[i] += sz[j]; }  
    count--;  
}

Quick-Union 和 Weighted Quick-Union 的比較：

可以發現，通過 sz 數組決定如何對兩棵樹進行合并之后，最后得到的樹的高度大幅度減小了。這是十分有意義的，因為在 Quick-Union 算法中的任何操作，都不可避免的需要調用 find 方法，而該方法的執行效率依賴于樹的高度。樹的高度減小了， find 方法的效率就增加了，從而也就增加了整個 Quick-Union 算法的效率。

上圖其實還可以給我們一些啟示，即對于 Quick-Union 算法而言，節點組織的理想情況應該是一顆十分扁平的樹，所有的孩子節點應該都在 height 為 1 的地方，即所有的孩子都直接連接到根節點。這樣的組織結構能夠保證 find 操作的最高效率。

那么如何構造這種理想結構呢？

在 find 方法的執行過程中，不是需要進行一個 while 循環找到根節點嘛？如果保存所有路過的中間節點到一個數組中，然后在 while 循環結束之后，將這些中間節點的父節點指向根節點，不就行了么？但是這個方法也有問題，因為 find 操作的頻繁性，會造成頻繁生成中間節點數組，相應的分配銷毀的時間自然就上升了。那么有沒有更好的方法呢？還是有的，即將節點的父節點指向該節點的爺爺節點，這一點很巧妙，十分方便且有效，相當于在尋找根節點的同時，對路徑進行了壓縮，使整個樹結構扁平化。相應的實現如下，實際上只需要添加一行代碼：

private int find(int p)  
{  
    while (p != id[p])  
    {  
        // 將p節點的父節點設置為它的爺爺節點  
        id[p] = id[id[p]];  
        p = id[p];  
    }  
    return p;  
}

至此，動態連通性相關的 Union-Find 算法基本上就介紹完了，從容易想到的 Quick-Find 到相對復雜但是更加高效的 Quick-Union ，然后到對 Quick-Union 的幾項改進，讓我們的算法的效率不斷的提高。

這幾種算法的時間復雜度如下所示：

Algorithm	Constructor	Union	Find
Quick-Find	N	N	1
Quick-Union	N	Tree height	Tree height
Weighted Quick-Union	N	lgN	lgN
Weighted Quick-Union With Path Compression	N	Very near to 1 (amortized)	Very near to 1 (amortized)

對大規模數據進行處理，使用平方階的算法是不合適的，比如簡單直觀的 Quick-Find 算法，通過發現問題的更多特點，找到合適的數據結構，然后有針對性的進行改進，得到了 Quick-Union 算法及其多種改進算法，最終使得算法的復雜度降低到了近乎線性復雜度。

如果需要的功能不僅僅是檢測兩個節點是否連通，還需要在連通時得到具體的路徑，那么就需要用到別的算法了，比如DFS或者BFS。

并查集的應用，可以參考另外一篇文章并查集應用舉例

來自：http://blog.jobbole.com/108359/

本文由用戶 StepanieGue 自行上傳分享，僅供網友學習交流。所有權歸原作者，若您的權利被侵害，請聯系管理員。

轉載本站原創文章，請注明出處，并保留原始鏈接、圖片水印。

本站是一個以用戶分享為主的開源技術平臺，歡迎各類分享！

本文地址：http://www.baiduhome.net/lib/view/open1480403497610.html

算法并查集