一、場景

有時候我們會遇到這樣的場景，比如:M={1,4,6,8},N={2,4,5,7}，我的需求就是判斷{1,2}是否屬于同一個集合，當(dāng)然實現(xiàn)方法有很多，一般情況下，普通青年會做出 O(MN)的復(fù)雜度，那么有沒有更輕量級的復(fù)雜度呢？并查集就是用來解決這個問題的。

二、操作

從名字可以出來，并查集其實只有兩種操作，并(Union)和查(Find)，并查集是一種算法，所以我們要給它選擇一個好的數(shù)據(jù)結(jié)構(gòu)，通常我們用樹來作為它的底層實現(xiàn)。

2.1、節(jié)點定義

 #region 樹節(jié)點
 /// <summary>
 /// 樹節(jié)點
 /// </summary>
 public class Node
 {
     /// <summary>
     /// 父節(jié)點
     /// </summary>
     public char parent;

     /// <summary>
     /// 節(jié)點的秩
     /// </summary>
     public int rank;
 }
 #endregion

2.2、Union 操作

<1> 原始方案首先我們會對集合的所有元素進行打散，最后每個元素都是一個獨根的樹，然后我們 Union 其中某兩個元素，讓他們成為一個集合，最壞情況下我們進行 M 次的 Union 時會存在這樣的一個鏈表的場景。

從圖中我們可以看到，Union 時出現(xiàn)了最壞的情況，而且這種情況還是比較容易出現(xiàn)的，最終導(dǎo)致在 Find 的時候就相當(dāng)復(fù)雜了，為 O(N)。

<2> 按秩合并我們發(fā)現(xiàn)出現(xiàn)這種情況的原因在于我們 Union 時都是將合并后的大樹作為小樹的孩子節(jié)點存在，那么我們在 Union 時能不能判斷一下，將小樹作為大樹的孩子節(jié)點存在，最終也就降低了新樹的深度，比如圖中的 Union(D,{E,F})的時候可以做出如下修改。

可以看出，我們有效的降低了樹的深度，在 N 個元素的集合中，構(gòu)建樹的深度不會超過 LogN 層。M 次操作的復(fù)雜度為 O(MlogN)，從代碼上來說，我們用 Rank 來統(tǒng)計樹的秩，可以理解為樹的高度，獨根樹時 Rank=0，當(dāng)兩棵樹的 Rank 相同時，可以隨意挑選合并，在新根中的 Rank++ 就可以了。

 #region 合并兩個不相交集合
 /// <summary>
 /// 合并兩個不相交集合
 /// </summary>
 /// <param name="root1"></param>
 /// <param name="root2"></param>
 /// <returns></returns>
 public void Union(char root1, char root2)
 {
     char x1 = Find(root1);
     char y1 = Find(root2);

     //如果根節(jié)點相同則說明是同一個集合
     if (x1 == y1)
         return;

     //說明左集合的深度 < 右集合
     if (dic[x1].rank < dic[y1].rank)
     {
         //將左集合指向右集合
         dic[x1].parent = y1;
     }
     else
     {
         //如果 秩 相等，則將 y1 并入到 x1 中，并將x1++
         if (dic[x1].rank == dic[y1].rank)
             dic[x1].rank++;

         dic[y1].parent = x1;
     }
 }
 #endregion

2.3、Find 操作

我們學(xué)算法，都希望能把一個問題優(yōu)化到不能優(yōu)化的地步，針對 logN 的級別，我們還能優(yōu)化嗎？當(dāng)然可以。

<1> 路徑壓縮在 Union 和 Find 這兩種操作中，顯然我們在 Union 上面已經(jīng)做到了極致，下面我們在 Find 上面考慮一下，是不是可以在 Find 上運用伸展樹的思想，這種伸展思想就是壓縮路徑。

從圖中我們可以看出，當(dāng)我 Find(F)的時候，找到“F”后，我們開始一直回溯，在回溯的過程中給，把該節(jié)點的父親指向根節(jié)點。最終我們會形成一個壓縮后的樹，當(dāng)我們再次 Find(F)的時候，只要 O(1)的時間就可以獲取，這里有個注意的地方就是 Rank，當(dāng)我們在路徑壓縮時，最后樹的高度可能會降低，可能你會意識到原先的 Rank 就需要修改了，所以我要說的就是，當(dāng)路徑壓縮時，Rank 保存的就是樹高度的上界，而不僅僅是明確的樹高度，可以理解成"伸縮椅"伸時候的長度。

 #region  查找x所屬的集合
 /// <summary>
 /// 查找x所屬的集合
 /// </summary>
 /// <param name="x"></param>
 /// <returns></returns>
 public char Find(char x)
 {
     //如果相等，則說明已經(jīng)到根節(jié)點了，返回根節(jié)點元素
     if (dic[x].parent == x)
         return x;

     //路徑壓縮(回溯的時候賦值，最終的值就是上面返回的"x"，也就是一條路徑上全部被修改了)
     return dic[x].parent = Find(dic[x].parent);
 }
 #endregion

我們注意到，在路徑壓縮后，我們將 LogN 的復(fù)雜度降低到 Alpha(N)，Alpha(N)可以理解成一個比 hash 函數(shù)還有小的常量，這就是算法的魅力。

到此這篇關(guān)于C#實現(xiàn)并查集的使用示例的文章就介紹到這了,更多相關(guān)C# 并查集內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！ 

最新評論