并查集(UnionFind)主要是用來解決圖論中「動(dòng)態(tài)連通性」問題的，數(shù)據(jù)結(jié)構(gòu)很簡(jiǎn)單碉克，卻能用來表示無向圖凌唬。簡(jiǎn)單的代碼如下：
class UnionFind {
int[] parent;
int cnt;
public UnionFind(int n) {
parent = new int[n];
for (int i=0; i<n; i++) {
parent[i] = i;
}
cnt = n;
}
public int find(int x) {
while (parent[x] != x) {
x = parent[x];
}
return x;
}
public void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py)
return;
parent[px] = py;
cnt--;
}
public int getCnt() {
return cnt;
}
}
可以看到代碼非常簡(jiǎn)單，僅僅用一個(gè)parent數(shù)組就可以表示一個(gè)圖了漏麦。使用0~n-1這n個(gè)數(shù)組下標(biāo)來表示圖中的n個(gè)節(jié)點(diǎn)客税，其中parent[x]=y表示x的父親是y。find函數(shù)查找節(jié)點(diǎn)x的祖先節(jié)點(diǎn)撕贞，union函數(shù)用來合并x和y節(jié)點(diǎn)的祖先更耻，也就是將兩個(gè)連通圖合并起來。cnt變量用來記錄所有的連通圖個(gè)數(shù)捏膨，每次合并后cnt減一秧均。
但是上面的代碼有個(gè)問題就是查找祖先的復(fù)雜度較高，如果所有節(jié)點(diǎn)剛好連成一個(gè)鏈表的話号涯，查找一次時(shí)間復(fù)雜度為O(n)目胡。
我們可以按如下兩種方式進(jìn)行優(yōu)化：
- 平衡性優(yōu)化：添加一個(gè)weight數(shù)組用來表示當(dāng)前連通圖的節(jié)點(diǎn)個(gè)數(shù)，合并x和y的祖先時(shí)链快，判斷兩個(gè)連通圖的weight大小誉己，把小的連到大的上。這樣可以保證整個(gè)圖盡量平衡域蜗，高度差不會(huì)太大巨双。
-
壓縮路徑：在find的時(shí)候加入一行代碼（parent[x] = parent[parent[x]]），把x的父親設(shè)置為父親的父親霉祸，也就是爺爺炉峰。這樣的話在查找x的祖先的過程中能把路徑的長(zhǎng)度縮小為一半。多次查找不同的節(jié)點(diǎn)的祖先后脉执，整個(gè)圖的高度會(huì)變成1疼阔。
話不多說，代碼優(yōu)化如下：
class UnionFind {
int[] parent;
int cnt;
int[] weight; // weight數(shù)組記錄連通圖的節(jié)點(diǎn)個(gè)數(shù)
public UnionFind(int n) {
parent = new int[n];
weight = new int[n];
for (int i=0; i<n; i++) {
parent[i] = i;
weight[i] = 1;
}
cnt = n;
}
public int find(int x) {
while (parent[x] != x) {
parent[x] = parent[parent[x]]; // 壓縮路徑
x = parent[x];
}
return x;
}
public void union(int x, int y) {
int px = find(x);
int py = find(y);
if (px == py)
return;
// 合并時(shí)根據(jù)weight來合并
if (weight[px] > weight[py]) {
parent[py] = px;
weight[px] += weight[py];
} else {
parent[px] = py;
weight[py] += weight[px];
}
cnt--;
}
public int getCnt() {
return cnt;
}
}
UnionFind最基礎(chǔ)的典型的使用就是判斷一個(gè)圖的連通分支數(shù)量。通過一個(gè)簡(jiǎn)單的例子來看看UnionFind的應(yīng)用婆廊，leetcode 547題——朋友圈：https://leetcode-cn.com/problems/friend-circles/
