算法概述
《Algorithms》（4th）在第一章第五節(jié)介紹了并查集算法（使用路徑壓縮的加權(quán) quick - union算法）男旗。該算法主要用于高效求解動(dòng)態(tài)連通性相關(guān)問題：
- 判斷指定兩點(diǎn)是否連通侥猬。
- 計(jì)算連通分量個(gè)數(shù)棕叫。
適用條件
- 點(diǎn)集固定杠人。
- 只允許動(dòng)態(tài)添加連通關(guān)系丘侠，不可動(dòng)態(tài)刪除連通關(guān)系惭嚣。
API
public class |
UF |
功能 |
|---|---|---|
UF(int N) |
初始化 N 個(gè)點(diǎn)饭望，序號(hào)為 0 ~ N - 1 | |
void |
union(int p, int q) |
在點(diǎn) p 與點(diǎn) q 之間添加連通關(guān)系 |
int |
find(int p) |
查詢點(diǎn) p 所在連通分量的標(biāo)識(shí)符 |
boolean |
connected(int p, int q) |
判斷點(diǎn) p 與點(diǎn) q 是否連通 |
int |
count() |
查詢連通分量的數(shù)量 |
實(shí)現(xiàn)代碼（Java）
public class UF {
private int[] id;
private int[] sz;
private int count;
public UF(int N) {
count = N;
id = new int[N];
for (int i = 0; i < N; ++i)
id[i] = i;
sz = new int[N];
for (int i = 0; i < N; ++i)
sz[i] = 1;
}
public void union(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if (pRoot == qRoot)
return;
if (sz[pRoot] < sz[qRoot]) {
id[pRoot] = qRoot;
sz[qRoot] = sz[pRoot] + sz[qRoot];
} else {
id[qRoot] = pRoot;
sz[pRoot] = sz[pRoot] + sz[qRoot];
}
count = count - 1;
}
public int find(int p) {
int oldP = p, tmp;
while (p != id[p])
p = id[p];
while (oldP != id[oldP]) {
tmp = id[oldP];
id[oldP] = p;
oldP = tmp;
}
return p;
}
public boolean connected(int p, int q) {
return find(p) == find(q);
}
public int count() {
return count;
}
}
算法詳解
算法使用樹（有根樹）表達(dá)連通分量，使用森林表示整個(gè)集合澈侠。
森林結(jié)構(gòu)
每個(gè)點(diǎn)都有對(duì)應(yīng)的 id 與 sz 值劫侧。id 為該點(diǎn)在樹中的父親的序號(hào)，樹根的 id 指向自身哨啃。只有樹根的 sz 值有意義烧栋，代表樹的大小，即連通分量中點(diǎn)的數(shù)目拳球。count 變量用于記錄森林中樹的個(gè)數(shù)审姓。
int count() 函數(shù)直接返回 count 變量，即連通分量的個(gè)數(shù)祝峻。
boolean connected(int p, int p) 函數(shù)中魔吐，先尋找兩個(gè)點(diǎn)所在樹的樹根。
- 如果樹根序號(hào)一致莱找，表示兩者在一棵樹（連通分量）中酬姆，返回
true。 - 如果樹根序號(hào)不同奥溺，返回
false辞色。
void union(int p, int q) 函數(shù)中，首先獲取兩個(gè)點(diǎn)對(duì)應(yīng)的樹根浮定。
- 如果兩點(diǎn)樹根相同淫僻，則已在同一連通分量中诱篷，為了保證樹結(jié)構(gòu)的性質(zhì)，直接退出雳灵，不再次連接兩點(diǎn)棕所。
- 如果不在同一分量中，需要將一棵樹設(shè)置為另一棵樹的子樹悯辙，合并兩個(gè)連通分量琳省。為了保證樹的平衡性，需要將規(guī)模較小的樹并入規(guī)模較大的樹中躲撰，更新小樹樹根的
id针贬，更新合并之后的樹根的sz，更新count連通分量個(gè)數(shù)拢蛋。
union 操作
int find(int p) 函數(shù)中首先備份查詢點(diǎn)的序號(hào)桦他，然后查詢至根節(jié)點(diǎn)。接下來將路徑上所有的節(jié)點(diǎn)的 id 都設(shè)置為根節(jié)點(diǎn)谆棱，壓縮樹的高度快压。
性能分析
該算法的所有操作的均攤時(shí)間復(fù)雜度在反 Ackermann 函數(shù)（α(x)）范圍之內(nèi)。對(duì)于任何實(shí)際的有意義的數(shù)字垃瞧，α(x) 小于 5蔫劣。
