并查集簡介

（2010-03-06）

1、定義

        并查集(union-find sets)是一種簡單的用途廣泛的集合。并查集是若幹個不相交集合（Disjoint Sets），能夠實作較快的集合合并和判斷元素所在集合的操作，應用很多。實際中通常采用樹形結構來表示并查集：每棵樹表示一個集合，不相交的集合則構成森林。一棵樹的每個節點包含如下資訊：父節點指針p[x]，樹的深度rank[x]。

2、操作

2.1 建立一個集合

      初始時，為每個元素x都建立一個集合：Make-Set(x)，集合的元素隻有它自己，僞代碼如下：

Make-Set(x)

　　 p[x]←x

　　 rank[x]←0

2.2 查找元素所在集合

       由于我們用一棵樹來表示集合，則為操作友善，每個集合有一個代表元素，我們将之定義為該樹的根，則查找元素x所在集合的操作Find-Set(x)僞代碼如下：

Find-Set(x)

　　if x=p[x]

　    then return x

　    else return Find-Set(p[x])

2.3 合并不相交集合

       合并元素a所在集合和元素b所在集合是将a所在樹的根節點的父節點改為b所在樹的根節點。這個操作Unin(a,b)隻需O(1)的時間。

Union(a,b)

　　Link(Find-Set(a),Find-Set(b))  

Link(a,b)

　　p[a]←b

由此可見Union的速度取決于Find-Set的速度。

3、優化

      上述Find-Set(x)操作的時間複雜度與樹的深度成線性關系，是以其平均時間複雜度為O(logN)，但在最壞情況下（樹退化成連結清單），時間複雜度為O(N)。是以有必要對算法進行優化。

3.1 啟發式合并

       在Link函數中，我們将深度較小的樹指到深度較大的樹的根上。這樣可以防止樹的退化，最壞情況不會出現。可以證明：這樣優化後樹的深度為O(log N)，是以Find-Set(x)的時間複雜度為O(log N)。改進後的Link函數僞代碼如下所示：

Link(a,b)

　　if rank[a]>rank[b]

　　then p[b]←a

　　else p[a]←b

　　   if rank[a]=rank[b]

　　   then rank[b]←rank[b]+1

3.2 路徑壓縮

      為了使得Find-Set(x)的效率更高，我們還要進行路徑壓縮，即在找到x的最遠祖先（集合代表根）時順便把查找路徑上的子孫的父節點直接改為該根，這樣以後Find-Set的時間複雜度可以認為是常數的。改進後的Find-Set僞代碼如下：

Find-Set(x)

        if p[x]≠x

　    then p[x]←Find-Set(p[x])

　    return p[x]

遞歸的程式有許多棧的操作，改成非遞歸會更快些：

Find-Set(x)

　    r←x

        while p[r]≠ r

　　   do r←p[r]

        while r≠x

　　   do q←p[x]

　　   p[x]←r

　　   x←q

       return r

3.3 時間複雜度

        經過啟發式合并和路徑壓縮之後的并查集進行n次查找的時間複雜度是O(nα(m,n))（執行n-1次合并和m>=n次查找）。其中α(m,n)是一個增長極其緩慢的函數，是Ackerman函數的某個反函數，它可以看作是小于5的。是以可以認為并查集的時間複雜度幾乎是線性的。

 【附】

Ackerman函數 一種雙遞歸函數，滿足以下定義：

Ackerman(1,0)=2 Ackerman(0,m)=1 ，m>=0 Ackerman(n,0)=n+2，n>=2 Ackerman(n,m)=Ackerman(Ackerman(n-1,m),m-1)， n,m>=1