快捷導(dǎo)航

C#實(shí)現(xiàn)并查集的使用示例

更新時(shí)間：2023年11月28日 10:10:58 作者：神仙別鬧

并查集是一種用于處理一些不相交集合的合并及查詢問(wèn)題的數(shù)據(jù)結(jié)構(gòu),具有高效、簡(jiǎn)潔、易用的特點(diǎn),本文主要介紹了C#實(shí)現(xiàn)并查集的使用示例,感興趣的可以了解一下

一、場(chǎng)景

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

二、操作

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

2.1、節(jié)點(diǎn)定義

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

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

2.2、Union 操作

<1> 原始方案首先我們會(huì)對(duì)集合的所有元素進(jìn)行打散，最后每個(gè)元素都是一個(gè)獨(dú)根的樹，然后我們 Union 其中某兩個(gè)元素，讓他們成為一個(gè)集合，最壞情況下我們進(jìn)行 M 次的 Union 時(shí)會(huì)存在這樣的一個(gè)鏈表的場(chǎng)景。

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

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

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

 #region 合并兩個(gè)不相交集合
 /// <summary>
 /// 合并兩個(gè)不相交集合
 /// </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é)點(diǎn)相同則說(shuō)明是同一個(gè)集合
     if (x1 == y1)
         return;

     //說(shuō)明左集合的深度 < 右集合
     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é)算法，都希望能把一個(gè)問(wèn)題優(yōu)化到不能優(yōu)化的地步，針對(duì) logN 的級(jí)別，我們還能優(yōu)化嗎？當(dāng)然可以。

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

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

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

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

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