并查集是算法4介紹的第一個算法赋续，我覺得很有意思，理解起來也不難外臂。它主要是解決圖論中「動態(tài)連通性」問題的。
此算法主要有兩個操作律胀，connected是返回兩個元素是否連通，union是合并兩個連通的元素集合貌矿。
首先用數(shù)組來表示炭菌，同一個集合的元素的值是相同的，如果合并集合逛漫，則需要修改某一集合的所有元素的值黑低，查詢是否屬于同一個集合只需要比較值是否相等即可。圖示如下：
image.png
代碼表示如下：
public class Union_Find {
private int[] id;
//初始化數(shù)組
public Union_Find(int N) {
for(int i = 0; i < N; i++) {
id[i] = i;
}
}
//判斷是否兩個元素是否連通
public boolean connected(int p, int q) {
return id[p] == id[q];
}
//連通兩個圖
public void union(int p, int q) {
int pid = id[p];
int qid = id[q];
for(int i = 0; i < id.length - 1; i++ ) {
if(id[i] == pid)
id[i] = qid;
}
}
}
上述代碼的合并集合時需要多次修改數(shù)組的元素酌毡，如果改用樹來表示就可以節(jié)省很多的修改次數(shù)克握。也是用一個一維數(shù)組。假設(shè)每個節(jié)點(diǎn)都指向它的父節(jié)點(diǎn)枷踏，根節(jié)點(diǎn)指向本身菩暗。一開始每個節(jié)點(diǎn)都是根節(jié)點(diǎn)，合并只需要把一個集合的根節(jié)點(diǎn)指向另一個集合的根節(jié)點(diǎn)就可以旭蠕。判斷是否同一個集合只要比較根節(jié)點(diǎn)是否相等即可停团。圖示如下：
代碼實(shí)現(xiàn)如下：
public class QuickFindUF {
private int[] id;
//初始化
public QuickFindUF(int N) {
for(int i = 0; i < N; i++) {
id[i] = i;
}
}
//尋找根節(jié)點(diǎn)
int root(int i) {
while(id[i] != i) {
i = id[i];
}
return i;
}
//判斷是否兩個元素是否連通
boolean connected(int p, int q) {
return root(p) == root(q);
}
//連通兩個圖
void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
id[rootP] = rootQ;
}
}
因?yàn)槭菢涞慕Y(jié)構(gòu)，如果樹不平衡掏熬，最差的情況會退化成鏈表佑稠，所有需要進(jìn)行一些優(yōu)化。
優(yōu)化一：增加size數(shù)組旗芬，記錄樹的權(quán)重舌胶，令小樹總是指向大樹。
void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if(rootP == rootQ) return;
//令小樹指向大樹
if(size[rootP] <= size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
}
else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
}
優(yōu)化二：可以在選在根節(jié)點(diǎn)的時候展平樹疮丛，只需要加一句代碼：
int root(int i) {
while(id[i] != i) {
//展平樹
id[i] = id[id[i]];
i = id[i];
}
return i;
}
完整代碼如下:
public class QuickFindUF {
private int[] id;
//初始化
private int[] size;
public QuickFindUF(int N) {
for(int i = 0; i < N; i++) {
id[i] = i;
size[i] = 1;
}
}
int root(int i) {
while(id[i] != i) {
id[i] = id[id[i]];
i = id[i];
}
return i;
}
boolean connected(int p, int q) {
return root(p) == root(q);
}
void union(int p, int q) {
int rootP = root(p);
int rootQ = root(q);
if(rootP == rootQ) return;
//令小樹指向大樹
if(size[rootP] <= size[rootQ]) {
id[rootP] = rootQ;
size[rootQ] += size[rootP];
}
else {
id[rootQ] = rootP;
size[rootP] += size[rootQ];
}
}
}
