博主按：因?yàn)榻坛趟緢D片使用的是 github 倉庫圖片，網(wǎng)速過慢的朋友請(qǐng)移步《并查集：集合合并與元素查找》原文地址铣卡。更歡迎來我的小站看更多原創(chuàng)內(nèi)容：godbmw.com，進(jìn)行“姿勢(shì)”交流 ?(?*)
1. 什么時(shí)候需要并查集？
在一些有 N 個(gè)元素的集合應(yīng)用問題中蛔糯，我們通常是在開始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元素的集合陈瘦，然后按一定順序?qū)儆谕唤M的元素所在的集合合并幌甘，其間要反復(fù)查找一個(gè)元素在哪個(gè)集合中。
這個(gè)過程就涉及到：“合并”和“查找”這兩個(gè)操作痊项。
利用并查集锅风，可以實(shí)現(xiàn)用數(shù)組存儲(chǔ)數(shù)據(jù)，并且查找操作和合并操作的時(shí)間復(fù)雜度近乎鞍泉。
2. 如何實(shí)現(xiàn)并查集皱埠？
2.1 實(shí)現(xiàn)查找操作
并查集是一種樹形數(shù)據(jù)結(jié)構(gòu)。在這些數(shù)據(jù)中咖驮，每個(gè)集合是一棵樹边器，所有的集合在一起就形成了“森林”训枢。
當(dāng)然，之前說過要節(jié)省空間忘巧，借助數(shù)組就可以實(shí)現(xiàn)恒界。為了方便說明，這里數(shù)組的索引值就是數(shù)據(jù)本身砚嘴，而索引 i 對(duì)應(yīng)的數(shù)組的值arr[i]就是i的根節(jié)點(diǎn)十酣。
如下圖所示。3际长、4耸采、9 這三個(gè)元素都以 8 位根節(jié)點(diǎn)。此時(shí)判斷兩個(gè)元素是否屬于同一集合也颤，只需要遞歸找到元素的根節(jié)點(diǎn)洋幻，比較根節(jié)點(diǎn)是否相同即可。
2.2 實(shí)現(xiàn)合并操作
這里的“合并”是指：將兩個(gè)元素所在的集合合并為一個(gè)集合翅娶。
這一步操作實(shí)現(xiàn)邏輯較復(fù)雜文留，假設(shè)有兩個(gè)元素 p 和 q 需要合并到一個(gè)集合，思路如下：
- 查找 p 和 q 的根節(jié)點(diǎn)竭沫，如果相同燥翅，兩個(gè)元素已經(jīng)是同一集合，跳出程序蜕提。如果不相同森书，往下執(zhí)行。
- 將其中一個(gè)根節(jié)點(diǎn)的重新指向另一個(gè)跟節(jié)點(diǎn)谎势，完成集合合并操作凛膏。
3. 算法分析和優(yōu)化
前面已經(jīng)說了，“并查集”是一種樹形數(shù)據(jù)結(jié)構(gòu)脏榆。而我們的查找和合并操作其實(shí)都是建立在從葉節(jié)點(diǎn)向上遞歸查找根節(jié)點(diǎn)的操作上猖毫。
因此，“并查集”的時(shí)間復(fù)雜度和樹的深度有關(guān)须喂，下面的優(yōu)化操作也是為了讓樹的深度盡可能少椿争，甚至變成 1 或者 2 層笆包。
3.1 合并優(yōu)化
如2.2所陳述伊者，這步操作： “將其中一個(gè)根節(jié)點(diǎn)的重新指向另一個(gè)跟節(jié)點(diǎn)喜每，完成集合合并操作” ，其實(shí)可能會(huì)造成樹的高度增加是己。例如下圖兩棵樹：
如果是右邊那棵樹的根節(jié)點(diǎn)指向了左邊樹的根節(jié)點(diǎn)又兵，那么，新形成的樹的高度就是 4卒废。然而沛厨，左邊那棵樹的根節(jié)點(diǎn)如果指向右邊那棵樹的跟節(jié)點(diǎn)乘盼，樹的高度就是 3。如此一來俄烁，形成的樹的高度更低绸栅。
優(yōu)化的方法就是：在“合并操作”的更改根節(jié)點(diǎn)指向的這步中，檢測(cè)兩棵樹的高度页屠，將高度較低的那顆樹指向高度較高的樹的根節(jié)點(diǎn)粹胯。所以，在初始化的時(shí)候辰企，需要多一個(gè)數(shù)組rank[]风纠，用來記錄以 i 為根節(jié)點(diǎn)的樹的高度。
3.2 “路徑壓縮”
大名鼎鼎的路徑壓縮牢贸，就是在“查找”的過程中竹观，將樹的高度壓縮成 2 層。如果對(duì)元素p調(diào)用了一次查找操作潜索，那么以p為葉子節(jié)點(diǎn)的往上一直到根節(jié)點(diǎn)的所有節(jié)點(diǎn)臭增，都會(huì)被壓縮。
如下圖所示竹习，在執(zhí)行find(4)操作后誊抛，整棵樹的樣子就變成了圖右邊的樣子。
代碼的實(shí)現(xiàn)整陌，需要借助遞歸拗窃，請(qǐng)直接看find()方法。
4. 代碼實(shí)現(xiàn)
關(guān)于并查集的數(shù)據(jù)結(jié)構(gòu)封裝在了頭文件union_find.h中：
// union_find.h
// Created by godbmw.com on 2018/10/9.
//
#ifndef UNIONFIND_UNION_FIND_H
#define UNIONFIND_UNION_FIND_H
#include <iostream>
#include <cassert>
using namespace std;
class UnionFind {
private:
int count;
// parent[i]：元素i父節(jié)點(diǎn)的索引值
int *parent;
// rank[i]：以i為根的集合所表示的樹的層數(shù)
int *rank;
public:
UnionFind(int count) {
this->count = count;
parent = new int[count];
rank = new int[count];
// 每個(gè)節(jié)點(diǎn)都是獨(dú)立的泌辫，所以父節(jié)點(diǎn)索引就是自己
// 每個(gè)節(jié)點(diǎn)的樹的高度都是1
for(int i = 0; i < count; i++) {
parent[i] = i;
rank[i] = 1;
}
}
~UnionFind() {
delete[] parent;
delete[] rank;
}
// 查找索引為p的元素的根節(jié)點(diǎn)的索引
int find(int p) {
// 路徑壓縮：將層數(shù)為n( n>1 )的樹壓縮為層數(shù)為1的樹
if( p != this->parent[p]) {
this->parent[p] = this->find( this->parent[p] );
}
return parent[p];
}
// 查看索引分別為p和q的元素是否屬于同一集合
bool is_connected(int p, int q) {
return this->find(p) == this->find(q);
}
// 合并索引分別p和q的元素到一個(gè)集合
void union_elements(int p, int q) {
int p_root = this->find(p), q_root = this->find(q);
// 根節(jié)點(diǎn)索引值相同：已經(jīng)屬于同一集合
if(p_root == q_root) return ;
if( this->rank[p_root] < this->rank[q_root] ) {
// 合并后随夸，q_root 的樹的深度并沒有改變
this->parent[p_root] = q_root;
} else if ( this->rank[q_root] < this->rank[p_root] ) {
// 合并后，p_root 的樹的深度并沒有改變
this->parent[q_root] = p_root;
} else {
// 合并后震放，q_root 的深度加 1
this->parent[p_root] = q_root;
this->rank[q_root] += 1;
}
}
};
#endif //UNIONFIND_UNION_FIND_H
5. 代碼測(cè)試
直接上了 1 億的數(shù)據(jù)量宾毒，并且執(zhí)行了 1 一次合并操作和 1 億次檢查是否屬于同一集合的操作。在我的電腦上耗時(shí)基本是 8s澜搅。有圖有真相：
測(cè)試代碼main.cpp如下：
// main.cpp
// created by godbmw.com
#include <iostream>
#include <ctime>
#include "union_find.h"
#define N 100000000
using namespace std;
void calc_run_time() {
srand(time(NULL));
register int a, b;
UnionFind uf = UnionFind(N);
time_t start_time = clock();
for(int i = 0; i < N; i++) {
a = rand() % N;
b = rand() % N;
uf.union_elements(a, b);
}
for(int i = 0; i < N; i++) {
a = rand() % N;
b = rand() % N;
uf.is_connected(a, b);
}
time_t end_time = clock();
cout << double(end_time - start_time) / CLOCKS_PER_SEC<<" s"<<endl;
}
int main() {
calc_run_time();
return 0;
}
