并查集（Union Find）

需求分析

假設現(xiàn)在有這樣一個需求潜必，如下圖的每一個點代表一個村莊活箕，每一條線就代表一條路，所以有些村莊之間有連接的路涯冠，有些村莊沒有連接的路炉奴，但是有間接連接的路

根據(jù)上面的條件，能設計出一個數(shù)據(jù)結(jié)構(gòu)蛇更，能快速執(zhí)行下面2個操作

1. 查詢兩個村莊之間是否有連接的路
2. 連接兩個村莊

為了完成上面的需求瞻赶，能不能使用前面介紹的數(shù)據(jù)結(jié)構(gòu)呢，例如：數(shù)組派任，鏈表砸逊，平衡二叉樹，集合掌逛？其實是可以的师逸，只是效率上高與低的問題。

例如使用動態(tài)數(shù)組完成上面這種操作豆混，可以通過下面的方式完成篓像。

1. 將每個圖用一個數(shù)組來對應，所以在這里皿伺，需要三個數(shù)組
   • 判斷兩個村莊之間是否有連接的路
     判斷兩個元素是否在同一個數(shù)組中即可员辩，如果兩個元素在同一個元素中，就代表它們之間鸵鸥，有連接的路奠滑，否則就沒有
   • 連接兩個村莊
     將兩個村莊的元素，整合到一個數(shù)組即可

其他幾種數(shù)據(jù)結(jié)構(gòu)操作也類似脂男。但是使用這些數(shù)據(jù)結(jié)構(gòu)存在一個問題养叛，它們的查詢，連接時間復雜度都是O(n)宰翅，所以用這些數(shù)據(jù)結(jié)構(gòu)來完成上面的需求弃甥，不合適。但是在本節(jié)內(nèi)容中介紹的并查集能夠辦到查詢汁讼，連接的均攤時間復雜度都是O(α(n)),α(n) < 5淆攻，所以并查集非常適合解決這類“連接”相關(guān)的問題

并查集

并查集和叫做不相交集合（Disjoint Set）

并查集有2個核心操作

1. 查找（Find）：查找元素所在的集合（這里的集合并不是特指Set這種數(shù)據(jù)結(jié)構(gòu)阔墩，是指廣義上的數(shù)據(jù)集合）
2. 合并（Union）：將兩個元素所在的集合合并為一個集合

并查集有2種常見的實現(xiàn)思路

1. Quick Find
   • 查找（Find）的時間復雜度為：O(1)
   • 合并（Union）的時間復雜度為：O(n)
2. Quick Union
   • 查找（Find）的時間復雜度為：O(logn)，可以優(yōu)化至O(α(n))瓶珊，α(n) ＜ 5
   • 合并（Union）的時間復雜度為：O(logn)啸箫，可以優(yōu)化至O(α(n))，α(n) ＜ 5

所以伞芹，通過Quick Find來實現(xiàn)并查集的話忘苛，查找的效率會比Quick Union高，但是合并效率會比Quick Union低唱较，那在開發(fā)中用哪一個呢扎唾？在開發(fā)中，一般使用Quick Union這種思路

并查集如何存儲數(shù)據(jù)

現(xiàn)假設并查集處理的數(shù)據(jù)都是整型南缓，那么可以用整型數(shù)組來存儲數(shù)據(jù)胸遇，其中數(shù)組的索引代表對應的元素編號，然后數(shù)組中存儲的數(shù)據(jù)為該元素對應所在的集合汉形，所以如果用下圖來表示對應村莊對應的集合纸镊，其中索引代表村莊的標號，編號對應的值代表村莊所在的集合

可以知道概疆，村莊0,1,3是相互有路相連逗威，村莊2/5分別獨立，沒有路與其他相連届案，村莊5,6,7是相互有路相連的庵楷。那么如果使用形象的圖來表示的話，村莊0,1,3楣颠，可以用下圖來進行表示

解釋：

1. 村莊索引0的父節(jié)點為村莊索引1
2. 村莊索引3的父節(jié)點為村莊索引1
3. 村莊索引1·的父節(jié)點為村莊索引1

也可以認為尽纽，索引對應的元素，代表父節(jié)點的索引童漩，所以每一個節(jié)點弄贿，都有一根線，指向其父節(jié)點矫膨，所以從這個圖差凹，可以看出，0,1,3的父節(jié)點都1侧馅，所以屬于同一個集合危尿。以此類推2表示單獨的一個集合

根據(jù)上面的定義，索引4的村莊的父節(jié)點索引為5馁痴，所以其實索引4與5之間是有聯(lián)系的谊娇，并且5,6,7,之間本來也存在聯(lián)系，所以最終可以用下圖來進行表示罗晕，所以可以認為4,5,6,7也是屬于同一個集合的济欢。

所以赠堵，如果并查集是整數(shù)的話，就可以通過數(shù)組來表示每個元素之間的關(guān)系法褥。所以并查集是可以用數(shù)組來實現(xiàn)的樹形結(jié)構(gòu)（二叉堆茫叭，優(yōu)先級隊列也是可以用數(shù)組實現(xiàn)的樹形結(jié)構(gòu)）

接口定義

所以，根據(jù)前面的介紹半等，并查集需要定義以下接口

/**
 * 查找v所屬的集合（根節(jié)點）
 */
int find(int v);
/**
 * 合并v1,v2所屬的集合
 */
void union(int v1, int v2);
/**
 * 檢查v1,v2是否屬于同一個集合
 */
boolean isSame(int v1, int v2);

初始化

前面介紹了并查集的兩種實現(xiàn)方式揍愁，不過，不管是使用哪種方式實現(xiàn)酱鸭，都需要對數(shù)據(jù)進行初始化吗垮，初始化時垛吗，每個元素各自屬于一個單元素集合凹髓。例如開始的時候，有如下的5個節(jié)點怯屉，其中索引0的元素存儲元素0蔚舀，索引1的元素存儲元素1，索引2的元素存儲元素2锨络，索引3的元素存儲元素3赌躺，索引4的元素存儲元素4

然后用圖來表示如下，其中羡儿，每一個元素屬于一個單元素集合礼患，即自己成為一個集合，這樣代表所有的元素都不在同一個集合內(nèi)掠归。

所以初始化的實現(xiàn)代碼為

public UnionFind(int capacity) {
    if (capacity < 0) {
        throw new IllegalArgumentException("capacity must be >= 1");
    }

    parents = new int[capacity];
    for (int i = 0; i < parents.length; i++) {
        parents[i] = i;
    }
}

Quick Find - Union

在使用Quick Find實現(xiàn)上圖的元素時缅叠，首先要進行的是初始化，前面已經(jīng)介紹過了虏冻，所以在這里就不再贅述肤粱。初始化完成后，如果現(xiàn)在需要對1,0執(zhí)行Union操作的話厨相，有兩種做法领曼，即將0的箭頭，指向1蛮穿，或者將1的箭頭指向0庶骄，這樣就代表兩個元素屬于同一個集合中。現(xiàn)規(guī)定践磅，如果執(zhí)行union(v1,v2)的話单刁，統(tǒng)一將v1的箭頭指向v2。所以音诈，如果現(xiàn)在執(zhí)行union(1,0)操作的話幻碱，只需要將索引為1指向的元素绎狭，值改為0即可。即下圖所示

對應的關(guān)系圖如下

同樣的褥傍，如果要執(zhí)行union(1,2)操作的話儡嘶，按照上面的操作，就是將索引為1指向的元素恍风，改為2即可

但是修改后有一個問題蹦狂，在以前，0,1是屬于同一個集合的朋贬，現(xiàn)在1凯楔，2要變?yōu)橥粋€集合，所以還需要將索引0指向的元素也修改為2

最終的關(guān)系圖如下

執(zhí)行union(4,0)操作的話锦募，根據(jù)上面的流程摆屯，最終得到的結(jié)果為

對應的關(guān)系圖如下

執(zhí)行union(3,2)，得到的結(jié)果為

執(zhí)行完成后得到的關(guān)系圖如下

所以糠亩，發(fā)現(xiàn)細節(jié)了嗎虐骑？使用Quick Find來實現(xiàn)Union的話，得到的結(jié)果很平赎线，每一個節(jié)點廷没，向上找一次，就能找到自己的根節(jié)點垂寥。那基于這種條件颠黎，繼續(xù)在研究如何實現(xiàn)Find操作

所以合并的實現(xiàn)代碼為

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    for (int i = 0; i < parents.length; i++) {
        if (parents[i] == p1) {
            parents[i] = p2;
        }
    }
}

Quick Find - Find

如果使用的是上面這種Union方式，可以發(fā)現(xiàn)滞项，數(shù)組中存儲的數(shù)據(jù)狭归，就是每個索引元素對應的根節(jié)點，所以如果有下圖的元素

對應的關(guān)系圖為

所以根據(jù)每個索引元素對應的根節(jié)點的結(jié)論可以知道蓖扑，如果執(zhí)行下面的操作

• find(0)得到的結(jié)果為2
• find(1)得到的結(jié)果為2
• find(3)得到的結(jié)果為3

所以Quick Find的Find操作唉铜，時間復雜度為O(1)

查找的實現(xiàn)為

public int find(int v) {
    rangeCheck(v);
    return parents[v];
}

所以，到這里律杠，通過Quick Find的方式潭流，就實現(xiàn)了并查集，不過柜去，從合并的實現(xiàn)可以發(fā)現(xiàn)鱼鸠，在合并時尝胆，需要對所有元素進行一次遍歷需五，所以合并的時間復雜度為O(n)燎窘。接下來，再來研究并查集的另外一種實現(xiàn)Quick Union

Quick Union- Union

前面說到，Quick Union的Find與Union時間復雜度都是O(logn)根盒，對比Quick Find中的Union時間復雜度O(n)來講钳幅，性能提升很多，接下來就看以下炎滞，Quick Union是如何實現(xiàn)的敢艰。

首先最開始的步驟與Quick Find是一樣的，都需要初始化册赛，每一個元素屬于一個單元素集合钠导。即下列的5個元素

組成單元素集合后

初始化完成后，就開始利用Quick Union的思路執(zhí)行Union操作森瘪。

執(zhí)行union(1,0)牡属，現(xiàn)依然規(guī)定，左邊的元素扼睬，跟隨右邊的元素逮栅，即這里合并后的話，是讓左邊元素的根節(jié)點痰驱，等于右邊元素的根節(jié)點证芭。即現(xiàn)在合并的1,0，其中1的根節(jié)點為1,0的根節(jié)點為0担映，由于左邊元素的根節(jié)點等于右邊元素的根節(jié)點，所以合并完成后叫潦，索引1的元素蝇完，根節(jié)點變?yōu)?，這一步矗蕊，看起來和Quick Find沒什么區(qū)別短蜕。

合并后的關(guān)系圖如下

接下來，如果繼續(xù)做union(1,2)操作的話傻咖，就有區(qū)別了朋魔。根據(jù)前面的結(jié)論，所以需要將索引1的根節(jié)點改為索引2的根節(jié)點卿操。由于現(xiàn)在1的根節(jié)點為0警检，2的根節(jié)點為2，所以只需要讓兩個根節(jié)點來處理就好了害淤，即讓0與2進行連接就好了扇雕，最終就是索引為0的節(jié)點，父節(jié)點變?yōu)?窥摄。

合并后的關(guān)系圖如下

繼續(xù)執(zhí)行union(4,1)操作镶奉，所以就是將4的根節(jié)點指向1的根節(jié)點，最終需要處理的節(jié)點就是4,2，達到的效果就是4指向2

合并后的關(guān)系圖如下

再執(zhí)行union(0,3)哨苛，也就是說需要將0,3進行合并鸽凶，仍然是找到0的根節(jié)點與3的根節(jié)點，然后將0根節(jié)點的父節(jié)點指向3的父節(jié)點即可

合并后的關(guān)系圖如下

所以建峭，最終看到的效果就是上圖這樣吱瘩，這種操作對比之前Quick Find做的union操作就不一樣了，Quick Find樹的高度迹缀，最多就是2使碾，但是采用Quick Union這種思路的話， 永遠都是找到根節(jié)點進行操作祝懂，情況就不一樣了票摇，Quick Find是將左邊集合中所有元素根節(jié)點，都改為右邊元素的根節(jié)點砚蓬，Quick只需要對左邊元素的根節(jié)點進行操作即可

所以實現(xiàn)代碼如下

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    parents[p1] = p2;
}

接下來在研究Find操作是如何實現(xiàn)的

Quick Union - Find

首先矢门，F(xiàn)ind操作的目的是要返回當前集合的根節(jié)點，所以例如下圖中的集合

對應的關(guān)系圖如下

如果要查找1的根節(jié)點灰蛙，就是從節(jié)點1開始祟剔，一直往上找，直到找到的節(jié)點摩梧，發(fā)現(xiàn)根節(jié)點是自己時物延，就說明已經(jīng)找到根節(jié)點了，將該根節(jié)點進行返回即可仅父。

所以

• find(0)得到的結(jié)果為2
• find(1)得到的結(jié)果為2
• find(3)得到的結(jié)果為3

Find操作的時間復雜度我O(logn)叛薯，由于Find的時間復雜度為O(logn)，所以Union操作的時間復雜度也為O(logn)

Find的實現(xiàn)代碼如下

public int find(int v) {
    rangeCheck(v);
    while (v != parents[v]) {
        v = parents[v];
    }
    return v;
}

這樣笙纤，Quick Union也實現(xiàn)了union與find操作耗溜。由于Quick Union與Quick Find之間時間復雜度的區(qū)別，所以建議使用性能更高的Quick Union省容。

Quick Union優(yōu)化

在Union的過程中抖拴，可能會出現(xiàn)樹不平衡的情況，甚至可能會退化成為鏈表腥椒，例如下圖

如果現(xiàn)在要執(zhí)行union(1,3)阿宅，按照以前的操作，是將1的根節(jié)點寞酿，指向3的根節(jié)點家夺，所以最終的結(jié)果如下

所以，如果一直按照這種方式進行合并的話伐弹，最終就真的會退化成為鏈表拉馋，一旦退化成為鏈表榨为，最終find操作的時間復雜度就變?yōu)镺(n)，所以需要對前面的方案進行優(yōu)化煌茴。

優(yōu)化方案

1. 基于size的優(yōu)化：將元素少的樹随闺，嫁接到元素多的樹
2. 基于rank的優(yōu)化：矮的樹，嫁接到高的樹

基于size的優(yōu)化

例如有下圖的兩個集合蔓腐，現(xiàn)在要將其合并

由于矩乐，現(xiàn)在是將元素少的樹，嫁接到元素多的樹上回论， 所以最終合并后的結(jié)果為

基于這種方式的實現(xiàn)散罕，需要知道每個集合中有多少個元素，所以傀蓉，要存儲以下每個集合的size欧漱，由于在初始化時，全是單元素集合葬燎，所以在初始化時误甚，也需要將size進行初始化，所以初始化的代碼如下

public UnionFind_QuickUnion_Size(int capacity) {
    super(capacity);
    sizes = new int[capacity];
    for (int i = 0; i < sizes.length; i++) {
        sizes[i] = 1;
    }
}

最終優(yōu)化的部分谱净，一定是合并集合的部分窑邦，所以只需要對union函數(shù)部分的代碼進行優(yōu)化就可以了

所以對size優(yōu)化后的代碼為

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    //size少的，嫁接到size多的上
    if (sizes[p1] > sizes[p2]) {
        parents[p2] = p1;//將p2嫁接到p1上
        sizes[p1] += sizes[p2];//更新size
    } else {
        parents[p1] = p2;
        sizes[p2] += sizes[p1];
    }
}

然后現(xiàn)在對前面的幾種實現(xiàn)壕探，利用相同數(shù)量的元素進行對比冈钦，最終得到的結(jié)果如下

可以看到，基于size的優(yōu)化浩蓉，速度非撑杉蹋快，效果非常明顯捻艳。

但是，基于size的優(yōu)化庆猫，也可能存在樹不平衡的問題认轨。

例如需要將下圖中的兩個集合進行合并

如果是使用基于size的優(yōu)化，最終合并的結(jié)果為

所以為了解決這種問題月培，將使用基于rank的優(yōu)化

基于rank的優(yōu)化

基于rank的優(yōu)化嘁字，是不比較集合中的數(shù)量，而是比較集合中樹的高度杉畜、基于樹高進行優(yōu)化的話纪蜒，現(xiàn)在對下圖中的兩個集合進行合并，則是將樹矮的樹此叠，合并到樹高的樹上

所以纯续，最終是將根節(jié)點為4的樹，嫁接上根節(jié)點為3的樹上，最終合并完成后如下

很明顯猬错，這種優(yōu)化窗看，從樹的平衡來講，樹會更加平衡倦炒，是由于基于size的優(yōu)化的显沈。

基于rank的優(yōu)化，同樣需要在初始化時逢唤，初始化每個單元素集合的高度進行初始化拉讯，所以初始化時的實現(xiàn)如下

private int[] ranks;
public UnionFind_QuickUnion_Rank(int capacity) {
    super(capacity);
    ranks = new int[capacity];
    for (int i = 0; i < ranks.length; i++) {
        ranks[i] = 1;
    }
}

與基于size的優(yōu)化相同，優(yōu)化的部分也是在合并時鳖藕，所以只需要對合并部分的代碼進行優(yōu)化即可魔慷。所以優(yōu)化后的代碼如下

public void union(int v1, int v2) {
    int p1 = find(v1);
    int p2 = find(v2);
    if (p1 == p2) return;
    //rank值小的，嫁接到rank值大的樹上
    if (ranks[p1] > ranks[p2]) {
        parents[p2] = p1; //將矮的樹吊奢，嫁接到高的樹上
        //由于是矮的樹嫁接到高的樹上盖彭，所以不需要更新樹高
    } else if (ranks[p1] < ranks[p2]){
        parents[p1] = p2;
    } else {
        //樹高相等，進行合并页滚，所以樹高會增加1
        parents[p1] = p2;
        ranks[p2] += 1;
    }
}

最終召边，將優(yōu)化后的兩種方案，用更大的測試數(shù)據(jù)進行測試后裹驰，得到的比較結(jié)果如下

可以發(fā)現(xiàn)隧熙，基于rank的優(yōu)化，表現(xiàn)同樣非常的優(yōu)秀幻林。不過需要注意贞盯，這并不意味著基于rank的優(yōu)化性能低于基于size的優(yōu)化，因為這兩種優(yōu)化沪饺，出發(fā)點不一樣躏敢。基于rank的優(yōu)化整葡，主要是為了解決基于size優(yōu)化中件余，出現(xiàn)不平衡的情況，建議使用基于rank的優(yōu)化遭居。

雖然兩種優(yōu)化啼器，效果都非常好，不過仍然還有進一步的優(yōu)化空間俱萍。接下來繼續(xù)研究關(guān)于優(yōu)化的問題

路徑壓縮（Path Compression）

什么叫路徑壓縮呢端壳？比如說現(xiàn)在有如下的兩個集合

現(xiàn)在基于Quick Union并且基于rank的優(yōu)化，進行union(1,5)合并的話枪蘑，得到的結(jié)果如下

合并后损谦，可以發(fā)現(xiàn)岖免，雖然有了基于rank的優(yōu)化，樹會相對平衡一點成翩，但是觅捆，隨著union的次數(shù)增加，樹的高度依然會越來越高麻敌，最終導致find操作會變得越來越慢栅炒。所以，基于這樣的問題的存在术羔，可以進行路徑壓縮優(yōu)化赢赊。

路徑壓縮

• 在find時使路徑上的所有節(jié)點都指向根節(jié)點，從而降低樹的高度

這句話的意思就是說级历，執(zhí)行完find操作以后释移，這條路徑上的所有節(jié)點，都直接指向根節(jié)點寥殖，所以例如執(zhí)行find(1)操作玩讳，執(zhí)行完成后的結(jié)果如下圖

可以發(fā)現(xiàn)，執(zhí)行完find操作后嚼贡，原來路徑上的節(jié)點2,3,4都直接指向了根節(jié)點熏纯，通過這樣的優(yōu)化，樹的高度僅進一步降低粤策，所以如果繼續(xù)執(zhí)行find(0),find(7)操作樟澜，最終在find后，路徑上的所有節(jié)點叮盘，都直接指向根節(jié)點秩贰，所以最終的結(jié)果如下

通過這樣的優(yōu)化后，以后在進行find操作時柔吼，就會變得非扯痉眩快。而且由于union也要使用到find愈魏，所以最終union效率也會提升蝗罗。所以，最終要達到的效果就是樹越矮越好蝌戒。接下來就研究，如何實現(xiàn)沼琉。

前面說到北苟，路徑壓縮是對find進行優(yōu)化，所以這次需要對find方法重新實現(xiàn)打瘪，最終find的實現(xiàn)如下

public int find(int v) {
    rangeCheck(v);
    if (v != parents[v]) {
        //修改v的父節(jié)點友鼻，通過遞歸調(diào)用傻昙，最終找到根節(jié)點，將v的父節(jié)點指向根節(jié)點
        //順便將整條路徑節(jié)點的父節(jié)點都修改為根節(jié)點
        parents[v] = find(parents[v]);
    }
    return parents[v];
}

通過優(yōu)化后彩扔，與size妆档，rank優(yōu)化進行對比，最終得到的結(jié)果如下

可以看到虫碉，最終的效果依然非常明顯贾惦。但是依然有以下注意點

1. 路徑壓縮使路徑上的所有節(jié)點都指向根節(jié)點，所以實現(xiàn)成本稍高敦捧，例如有遞歸調(diào)用须板，會開辟更多的棧空間

所以兢卵，基于這種問題习瑰，還有另外2中更優(yōu)的做法，不僅能降低樹高秽荤，實現(xiàn)成本也會比路徑壓縮更低甜奄，分別為

1. 路徑分裂（Path Spliting）
2. 路徑減半（Path Halving）

路徑分裂，路徑減半的效率差不多窃款，但都比路徑壓縮要好

路徑分裂（Path Spliting）

路徑分裂：使路徑上的每個節(jié)點都指向其祖父節(jié)點（parent的parent）

例如课兄，下列的集合

在執(zhí)行find(1)操作時，會將1指向3,3指向5,5指向7,2指向4,4指向6,6指向7雁乡，所以最終執(zhí)行完畢后的結(jié)果如下圖

所以第喳，可以看到，使用了路徑分裂這種優(yōu)化方案的話踱稍， 樹的高度的確是降低了曲饱，不像路徑壓縮一樣，直接將所有子節(jié)點平鋪開珠月。所以拆分的成本會比路徑壓縮低一些扩淀。所以基于這種思路，最終實現(xiàn)的代碼如下

public int find(int v) {
    rangeCheck(v);
    while (v != parents[v]) {
        //將當前節(jié)點的父節(jié)點保存下來
        int p = parents[v];
        //然后讓當前節(jié)點指向祖父節(jié)點
        parents[v] = parents[parents[v]];
        //更新節(jié)點,重復執(zhí)行操作
        v = p;
    }
    return v;
}

通過與前面幾種優(yōu)化方案進行對比啤挎，最終得到的比較結(jié)果如下

可以發(fā)現(xiàn)驻谆，路徑分裂方案確實進一步優(yōu)化了性能。說明這種路徑分裂方案是可行的庆聘，那接下來再研究路徑減半這種優(yōu)化方案胜臊。

路徑減半（Path Halving）

路徑減半：使路徑上的每隔一個節(jié)點就指向其祖父節(jié)點（parent的parent）

對比前面的路徑分裂，路徑分裂是每一個節(jié)點伙判，都指向祖父節(jié)點象对，路徑減半是每隔一個節(jié)點就指向祖父節(jié)點。那究竟是什么意思呢宴抚？例如有下圖的集合

現(xiàn)在執(zhí)行find(1)操作勒魔，根據(jù)上面的定義甫煞，即執(zhí)行完find(1)后，1指向祖父節(jié)點冠绢，3指向祖父節(jié)點抚吠，5指向祖父節(jié)點，即3指向5,5指向7弟胀，其余元素保持不變楷力，所以最終的結(jié)果如下圖

其實可以發(fā)現(xiàn)，這種方案對比前面的路徑分裂邮利，效果類似弥雹。因為最紅優(yōu)化后的樹高，是一樣的⊙咏欤現(xiàn)在已經(jīng)知道了優(yōu)化辦法剪勿，根據(jù)這種優(yōu)化辦法，最終得到的優(yōu)化代碼如下

public int find(int v) {
    rangeCheck(v);
    while (v != parents[v]) {
        //然后讓當前節(jié)點指向祖父節(jié)點
        parents[v] = parents[parents[v]];
        //parents[v]為祖父節(jié)點方庭，祖父節(jié)點重復執(zhí)行操作
        v = parents[v];
    }
    return v;
}

最終通過下圖幾種優(yōu)化方案的對不厕吉，可以發(fā)現(xiàn)，路徑減半和路徑分裂的性能很接近

理論上來講械念，路徑減半與路徑分裂兩種算法头朱，都非常優(yōu)秀。并且總體來講龄减，都要由于其他優(yōu)化方案项钮。

總結(jié)

摘自《維基百科》：https://en.wikipedia.org/wiki/Disjoint-set_data_structure

大概意思是

1. 使用路徑壓縮，分裂或者減半 + 基于rank或者size的優(yōu)化
   • 可以確保每個操作的均攤時間復雜度為O(α(n))希停，α(n) < 5

個人建議的搭配

1. Quick Union
2. 基于rank的優(yōu)化
3. Path Halving或者Path Spliting

自定義類型

之前的使用都是基于整型數(shù)據(jù)烁巫，如果其他自定義類型也想使用并查集，如何實現(xiàn)呢宠能？可以參考以下方案

1. 通過一些方法亚隙，將自定義類型轉(zhuǎn)換為整型后，使用并查集（比如生成哈希值）
2. 使用鏈表+映射（Map）

為什么可以使用鏈表實現(xiàn)呢违崇？因為并查集本質(zhì)上就是樹形結(jié)構(gòu)阿弃，只不過是通過數(shù)組來表達這種樹形結(jié)構(gòu)。然后樹形結(jié)構(gòu)中的每一條分支羞延，都是一條鏈表渣淳。

demo下載地址

完！