一、場(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ù)雜度，那么有沒有更輕量級(jí)的復(fù)雜度呢？并查集就是用來解決這個(gè)問題的。

二、操作

從名字可以出來，并查集其實(shí)只有兩種操作，并(Union)和查(Find)，并查集是一種算法，所以我們要給它選擇一個(gè)好的數(shù)據(jù)結(jié)構(gòu)，通常我們用樹來作為它的底層實(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ì)超過 LogN 層。M 次操作的復(fù)雜度為 O(MlogN)，從代碼上來說，我們用 Rank 來統(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)相同則說明是同一個(gè)集合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é)算法，都希望能把一個(gè)問題優(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”后，我們開始一直回溯，在回溯的過程中給，把該節(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 就需要修改了，所以我要說的就是，當(dāng)路徑壓縮時(shí)，Rank 保存的就是樹高度的上界，而不僅僅是明確的樹高度，可以理解成"伸縮椅"伸時(shí)候的長(zhǎng)度。

 #region  查找x所屬的集合/// <summary>/// 查找x所屬的集合/// </summary>/// <param name="x"></param>/// <returns></returns>public char Find(char x){//如果相等，則說明已經(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ù)還有小的常量，這就是算法的魅力。