目錄

1成箫、等價關(guān)系和等價類

2谬俄、并查集實現(xiàn)中的權(quán)衡

2.1上炎、快速FIND實現(xiàn)（Quick FIND）

2.2檀何、快速UNION實現(xiàn)（Quick UNION）

2.2.1击敌、快速UNION實現(xiàn)（慢FIND）

2.2.2坐搔、快速UNION實現(xiàn)（快FIND）

2.2.3内列、利用路徑壓縮來實現(xiàn)快速UNION

2.3寄啼、小結(jié)

正文

1纽哥、等價關(guān)系和等價類

• 假定S是集合钠乏，它包含元素和定義在集合上的關(guān)系R。對于集合中的每一對元素a春塌，b∈S晓避，aRb要么為真簇捍，要么為假。如果aRb為真俏拱，則a與b 相關(guān)暑塑，否則為 不相關(guān)。如果一個關(guān)系滿足以下三種性質(zhì)锅必，則關(guān)系是 等價關(guān)系：
  1）自反性：對于任意元素a∈S事格，aRa為真。
  2）對稱性：對于任意兩個元素a搞隐，b∈S驹愚，如果aRb為真，那么bRa也為真劣纲。
  3）傳遞性：對于任意三個元素a逢捺，b，c∈S癞季，如果aRb為真劫瞳，bRc為真，那么aRc也為真余佛。

• 【 例子】：鐵路連接是一種等價關(guān)系柠新。因為任何位置都能連接它自身，所以它是自反的辉巡。如果城市a與城市b之間有個連接線恨憎，那么城市b也能連接城市a，所以它是對稱的郊楣。如果城市a連接城市b且城市b連接城市c憔恳，那么城市a也能連接城市c。

• 元素a∈S的 等價類 是S的一個子集净蚤，該子集包含所有與a 相關(guān) 的元素钥组。 等價類 對集合S產(chǎn)生一個分割，S中的每個成員都屬于一個 等價類 中今瀑，那么判斷aRb是否為真程梦，需要判斷兩者是否屬于同一個 等價類 中。

• 任意兩個 等價類 的交集為空橘荠，所以 等價類 有時候也叫 并查集屿附，包括以下三個基本操作：
  1）創(chuàng)建一個等價類（MAKESET(X)：創(chuàng)建包含元素X的新集合）。
  2）查找等價類（FIND(X)：返回包含元素X的集合）哥童。
  3）合并等價類（UNION(X,Y)：通過合并元素X和Y來產(chǎn)生新集合挺份，同時刪除包含X和Y的原集合）。

2贮懈、并查集實現(xiàn)中的權(quán)衡

• 初始時匀泊，假設(shè)輸入n個集合优训，每個集合僅有一個元素。這說明初始表示所有關(guān)系都是假的（自反性除外）各聘。每個集合都有不同元素揣非，因此 Si∩Sj=空。

• 為添加關(guān)系aRb伦吠，需要首先檢查a和b是否已經(jīng) 相關(guān) 妆兑。可以通過在a和b上執(zhí)行 FIND 操作來驗證毛仪，并判斷它們是否屬于同一個 等價類 中搁嗓。如果不在，那么就執(zhí)行 UNION 操作箱靴。該操作將包含a和b的兩個等價類 合并 到一個新的等價類腺逛，即創(chuàng)建集合 Sk=Si∪Sj，同時刪除集合Si和Sj衡怀。有以下兩種方法實現(xiàn) FIND/UNION操作：
  1）快速FIND實現(xiàn)（也叫Quick FIND）棍矛。
  2）快速UNION實現(xiàn)（也叫Quick UNION）。

2.1抛杨、快速FIND實現(xiàn)（Quick FIND）

• 可以使用數(shù)組來實現(xiàn)够委，如下圖所示2-1所示，假定所有元素都是按0~n-1編號怖现，元素0的集合是3茁帽，元素2的集合是5，以此類推屈嗤。

  
  
  圖2-1 數(shù)組實現(xiàn)Quick FIND

• FIND操作便只需要O(1)時間潘拨。為了執(zhí)行 UNION(a,b)（假定a在集合i，b在集合j中）饶号，需要掃描整個數(shù)組铁追，并將所有i中元素轉(zhuǎn)移到j中，這需要花費 O(n) 時間茫船。在最壞情況下琅束，n-1個并集操作序列需要的時間為 O(n^2 )。如果有O(n^2)個FIND操作算谈，那么平均時間復雜度為 O(1)涩禀。如果FIND操作很少，那么該時間復雜度就是不可接受的濒生。

2.2、快速UNION實現(xiàn)（Quick UNION）

2.2.1幔欧、快速UNION實現(xiàn)（慢FIND）

• 當且僅當元素在同一個集合時罪治，FIND 操作才返回相同的值丽声。在表示并查集時，主要目標是為每一組賦予不同的集合觉义⊙闵纾可以通過 樹 來實現(xiàn)，因為每一個元素只有一個 根結(jié)點晒骇，可以使用它作為集合霉撵。

• 通過數(shù)組實現(xiàn)，對于每個元素洪囤，將保存元素的 雙親結(jié)點徒坡，為了區(qū)分根結(jié)點，假定數(shù)組根結(jié)點的雙親結(jié)點與其相同瘤缩。定義如下操作：
  1）MAKESET(X)：創(chuàng)建一個新集合喇完，它只包含一個元素X，并在數(shù)組中更新X的雙親結(jié)點為X剥啤。這就意味著X的根結(jié)點是X锦溪。如圖2-2所示。
  

  圖2-2 MAKESET(X)
  
  2）UNION(X,Y)：合并包含X和Y的兩個集合府怯，用合并后的集合替換這兩個集合刻诊，并在此數(shù)組中將X的雙親結(jié)點更新為Y。如圖2-3所示牺丙。
  
  圖2-3 UNION(X,Y)
  
  3）FIND(X)：返回元素X所在的集合则涯，持續(xù)查找X的集合直至達到樹的根結(jié)點。如圖2-4所示赘被。
  
  圖2-4 FIND(X)

• 例子：對于元素0~6是整，初始表示如圖2-5所示：
  

  圖2-5 初始圖
  
  1）執(zhí)行完UNION(5,6)后，如圖2-6所示：
  
  圖2-6 UNION(5,6)
  
  2） 執(zhí)行完UNION(1,2)后民假，如圖2-7所示：
  
  圖2-7 UNION(1,2)
  
  3） 執(zhí)行完UNION(0,2)后浮入，如圖2-8所示：
  
  圖2-8 UNION(0,2)
  
  【這里的一個要點是，UNION操作只改變根結(jié)點的雙親結(jié)點而不改變集合中其他元素的雙親結(jié)點羊异。由此事秀，UNION操作的時間復雜度為 O(1)，F(xiàn)IND(X)操作的時間復雜度與X在該樹中的深度成 正比野舶。最壞情況下易迹，F(xiàn)IND操作的運行時間是O(n)，m個連續(xù)的FIND操作需要O(mn)】

• 代碼實現(xiàn)：

    /// <summary>
    /// 快速UNION（慢FIND）
    /// </summary>
    public class DisjointSet {
        /// <summary>
        /// 集合
        /// </summary>
        public int[] S { get; set; }

        /// <summary>
        /// 集合中元素的個數(shù)
        /// </summary>
        public int size { get; set; }

        /// <summary>
        /// 初始化集合
        /// </summary>
        /// <param name="size"></param>
        public void MAKESET(int size) {
            S = new int[size];
            for (int i = size-1; i >=0; i--) {
                S[i] = i;
            }
        }

        /// <summary>
        /// FIND
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        public int FIND(int x) {
            if (!(x >= 0 && x < size)) {
                return -1;
            }
            if (S[x] == x) {
                return x;
            }
            else {
                return FIND(S[x]);
            }
        }

        /// <summary>
        /// UNION
        /// </summary>
        /// <param name="root1"></param>
        /// <param name="root2"></param>
        public void UNION(int root1,int root2) {
            if (FIND(root1) == FIND(root2)) {
                return;
            }
            if (!((root1 >= 0 && root1 < size) && (root2 >= 0 && root2 < size))) {
                return;
            }
            S[root1] = root2;
        }
    }

2.2.2平道、快速UNION實現(xiàn)（快FIND）

• 上述方法的主要問題是睹欲，在最壞情況下會得到一棵斜樹，并且時間復雜度為O(n)，有以下兩種方式改進窘疮。
  1）基于大小的UNION（也叫基于重量的UNION）：使較小的樹作為較大樹的一棵子樹袋哼。
  2）基于高度的UNION（也叫基于秩的UNION）：使高度較小的樹作為高度較大的一棵子樹。

1）基于大小的UNION

• 前面的表示中闸衫，對于每個元素i涛贯，若該元素是 根元素，則存儲i蔚出。而本方法則 存儲樹的大小的負值（即弟翘，如果樹的大小為3，則根結(jié)點元素需要在數(shù)組中存儲-3）骄酗。假定包含一個元素的集合大小為1稀余，且存儲為-1。圖2-8的例子酥筝，用該方法后的表示如圖2-9所示滚躯。
  
  圖2-9 基于大小的UNION
• 代碼實現(xiàn)：

        /// <summary>
        /// UNION（基于大小）
        /// </summary>
        /// <param name="root1"></param>
        /// <param name="root2"></param>
        public void UNIONBySize(int root1,int root2) {
            if (FIND(root1) == FIND(root2)) {
                return;
            }
            if (S[root2] < S[root1]) {
                S[root2] += S[root1];
                S[root1] = root2; 
            }
            else {
                S[root1] += S[root2];
                S[root2] = root1;
            }
        }

2）基于高度的UNION

• 與基于大小的UNION類似嘿歌，本方法 存儲樹的高度的負值掸掏，假定只有一個元素的樹的高度為1。圖2-8的例子宙帝，用該方法后的表示如圖2-10所示丧凤。
  
  圖2-10 基于高度的UNION
• 代碼實現(xiàn)：

        /// <summary>
        /// UNION（基于高度）
        /// </summary>
        /// <param name="root1"></param>
        /// <param name="root2"></param>
        public void UNIONByHeight(int root1,int root2) {
            if (FIND(root1) == FIND(root2)) {
                return;
            }
            if (S[root2] < S[root1]) {
                S[root1] = root2;
            }
            else {
                if (S[root2] == S[root1]) {
                    S[root1]--;
                }
                S[root2] = root1;
            }
        }

3）比較基于大小的UNION和基于高度的UNION

• 使用基于大小的UNION，任意結(jié)點的高度永遠不會大于logn步脓，當由于UNION操作使其高度增加時愿待，它被放置在至少是原來 2倍 大小的樹中。即它的高度最多是以 logn 倍增加的靴患。FIND操作的時間復雜度為 O(logn)仍侥，m次連續(xù)執(zhí)行該操作需要 O(mlogn) 的時間。
• 如果對于兩棵相同高度的樹進行UNION操作鸳君，樹的高度會比之前的 高度增加1农渊，否則就等于 高度最大 的那個。這就使得n個結(jié)點的樹的高度增長的倍數(shù) 大于O(logn)或颊，m次連續(xù)執(zhí)行該操作仍然需要 O(mlogn) 的時間砸紊。

2.2.3、利用路徑壓縮來實現(xiàn)快速UNION

• FIND操作遍歷從當前結(jié)點到根結(jié)點路徑的一系列結(jié)點囱挑，通過將這些結(jié)點的每個 父指針直接指向根結(jié)點醉顽，可以使后面的FIND操作更高效，這個過程叫做 路徑壓縮平挑。

• 對FIND函數(shù)游添，使用路徑壓縮的唯一改變是S[X]的值等于FIND函數(shù)的返回值系草。通過遞歸地尋找該結(jié)點集合的根結(jié)點，然后令X直接指向根結(jié)點唆涝。如圖2-11所示悄但。

  
  
  圖2-11 路徑壓縮

• 代碼實現(xiàn)：

        /// <summary>
        /// 路徑壓縮FIND
        /// </summary>
        /// <param name="x"></param>
        /// <returns></returns>
        public int FIND2(int x) {
            if (!(x >= 0 && x < size)) {
                return -1;
            }
            if (S[x] <= 0) {
                return x;
            }
            else {
                S[x] = FIND2(S[x]);
                return S[x];
            }
        }

【注意：路徑壓縮與基于大小的UNION兼容，但與基于高度的UNINO不兼容石抡，因為沒有有效的方法來改變樹的高度】

2.3、小結(jié)

• 在包含n個對象的集合中執(zhí)行m次的UNION-FIND操作助泽，最壞情況的時間復雜度如下所示啰扛。