1.概述
并查集是一種樹形的數(shù)據(jù)結(jié)構(gòu)璃弄，但是這種樹很特殊纤掸，每棵樹都是從子節(jié)點(diǎn)指向父節(jié)點(diǎn)的政己，在使用中也常常以森林來表示掏愁，用于解決一些不相交集合的合并和查詢問題歇由。
上面的概念有點(diǎn)抽象托猩，其實(shí)并查集就是用來解決連接問題印蓖，并查集的查詢其實(shí)就是判斷兩個(gè)元素是否屬于同一個(gè)集合，兩個(gè)元素屬于同一個(gè)集合京腥，那么他們就是連接的，否則不連接溅蛉。并查集的并其實(shí)就是將不在同一個(gè)集合的兩個(gè)元素合并公浪，使其處于同一集合他宛，在樹中也就是表現(xiàn)的兩個(gè)元素的節(jié)點(diǎn)連在一起或連在同一個(gè)父節(jié)點(diǎn)上。下面用圖示說明此問題欠气。
上圖一數(shù)字 1—9各自都為一個(gè)集合厅各，都是一棵只有根節(jié)點(diǎn)的樹，相互沒有連接预柒，這九棵樹組成森林队塘。
上圖二4和6組合，4為根節(jié)點(diǎn)宜鸯。 1,憔古、2、5組合成一棵樹淋袖，3鸿市、8、9即碗、7組合成一棵樹焰情，但是1、2剥懒、5是按深度優(yōu)先組合内舟，3、8初橘、9谒获、7是按廣度優(yōu)先組合，廣度優(yōu)先組合比深度優(yōu)先組合后樹的深度要小壁却，查找時(shí)效率較高批狱。
上圖中如果將圖一中的5和4組合，5和6組合展东，其結(jié)果都是圖二赔硫，因?yàn)?和4組合就是將5所在樹的根節(jié)點(diǎn)2指向4所在樹的根節(jié)點(diǎn)，4本身就是根節(jié)點(diǎn)盐肃，即將2指向4即可爪膊。5和6組合也是將5所在的根節(jié)點(diǎn)2指向6所在樹的根節(jié)點(diǎn)4，其實(shí)是完全一樣的砸王。
2.并查集的實(shí)現(xiàn)
1.數(shù)組實(shí)現(xiàn)：用數(shù)組存儲集合的id,兩個(gè)元素集合id相同說明在同一個(gè)集合推盛，不同則不在同一個(gè)集合。初始時(shí)每一個(gè)元素對應(yīng)一個(gè)集合id,每一個(gè)元素都屬于一個(gè)不同的集合谦铃，將兩個(gè)元素組合耘成，就是遍歷數(shù)組將這兩個(gè)元素的集合id設(shè)置為同一個(gè)集合id，此時(shí)的時(shí)間復(fù)雜度為O(n)。查找時(shí)瘪菌，只需要返回查找元素的集合id即可撒会，所以查找的時(shí)間復(fù)雜度為O(1)，因此师妙，這種并查樹的實(shí)現(xiàn)也成為：Quick Find诵肛。
java代碼：
UF.java(接口定義)
public interface UF {
int getSize();
boolean isConnected(int p,int q);
void unionElements(int p,int q);
}
實(shí)現(xiàn)代碼
public class UnionFind1 implements UF {
int[] id; //存放集合id
public UnionFind1(int size){
id = new int[size];
for (int i = 0; i < id.length; i++) {
id[i] = i; //初始化時(shí)每一個(gè)元素對應(yīng)一個(gè)集合id，id數(shù)組中的每一個(gè)元素都不相同,每一個(gè)元素都沒有和其他元素合并
}
}
@Override
public int getSize() {
return id.length;
}
//查找索引為i的集合id
private int find(int i){
if(i < 0 || i>= id.length)
throw new IllegalArgumentException("非法索引");
return id[i];
}
//判斷p和q是否連接
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//將p和q連接
@Override
public void unionElements(int p, int q) {
int pID = find(p);
int qID = find(q);
if(pID == qID)
return;
for (int i = 0; i < id.length; i++) {
if(id[i] == pID)
id[i] = qID;
}
}
}
2.使用樹實(shí)現(xiàn)并查集：由子節(jié)點(diǎn)指向父節(jié)點(diǎn)的樹默穴，將父節(jié)點(diǎn)對應(yīng)的元素存儲在數(shù)組中怔檩，初始時(shí)父節(jié)點(diǎn)對應(yīng)元素的數(shù)組中每個(gè)元素都不相同，表示每個(gè)節(jié)點(diǎn)都是父節(jié)點(diǎn)蓄诽，都沒有相連薛训。兩個(gè)元素組合時(shí)，將其對應(yīng)的父節(jié)點(diǎn)的數(shù)組元素設(shè)置為相同即可若专，此時(shí)合并和查下的時(shí)間復(fù)雜度都為O(h),h為樹的深度许蓖，相比較組合時(shí)要比數(shù)組實(shí)現(xiàn)的O(n)要快概漱，因此這種并查集的實(shí)現(xiàn)也稱作：Quick Union
java代碼：
public class UnionFind2 implements UF{
int[] parent;
public UnionFind2(int size){
parent = new int[size];
for (int i = 0; i < size; i++) {
parent[i] = i;
}
}
@Override
public int getSize() {
return parent.length;
}
//查找i對應(yīng)的集合編號
//時(shí)間復(fù)雜度為O（h）,h為樹的高度
private int find(int i){
if(i < 0 || i>= parent.length)
throw new IllegalArgumentException("非法索引");
while (i != parent[i])
i = parent[i];
return i;
}
@Override
public boolean isConnected(int p, int q) {
return find(p) == find(q);
}
//合并操作
//時(shí)間復(fù)雜度為O（h）,h為樹的高度
@Override
public void unionElements(int p, int q) {
int pRoot = find(p);
int qRoot = find(q);
if(pRoot == qRoot)
return;
parent[pRoot] = qRoot;
}
}
接下來大致的測一下用數(shù)組實(shí)現(xiàn)和用樹實(shí)現(xiàn)并查集的速度差異：
測試代碼：
public class Test {
private static double testUF(UF uf,int m){
int size = uf.getSize();
Random random = new Random();
long startTime = System.nanoTime();
for (int i = 0; i < m; i++) {
int a = random.nextInt(size);
int b = random.nextInt(size);
uf.unionElements(a,b);
}
for (int i = 0; i < m; i++) {
int a = random.nextInt(size);
int b = random.nextInt(size);
uf.isConnected(a,b);
}
long endTime = System.nanoTime();
return (endTime - startTime) / 1000000000.0;
}
public static void main(String[] args) {
int size = 10000;
int m = 10000;
UnionFind1 unionFind1 = new UnionFind1(size);
System.out.println("UnionFind1: " + testUF(unionFind1,m) + " s");
UnionFind2 unionFind2 = new UnionFind2(size);
System.out.println("UnionFind2: " + testUF(unionFind2,m) + " s");
/*UnionFind3 unionFind3 = new UnionFind3(size);
System.out.println("UnionFind3: " + testUF(unionFind3,m) + " s");
UnionFind4 unionFind4 = new UnionFind4(size);
System.out.println("UnionFind4: " + testUF(unionFind4,m) + " s");
UnionFind5 unionFind5 = new UnionFind5(size);
System.out.println("UnionFind5: " + testUF(unionFind5,m) + " s");
UnionFind6 unionFind6 = new UnionFind6(size);
System.out.println("UnionFind6: " + testUF(unionFind6,m) + " s");*/
}
}
上面的測試代碼執(zhí)行了兩個(gè)方法：uf.unionElements(a,b)和 uf.isConnected(a,b)减俏。對于數(shù)組實(shí)現(xiàn)的uf.isConnected(a,b)方法時(shí)間復(fù)雜度為O(1), uf.isConnected(a,b)方法復(fù)雜度為O(n),執(zhí)行次數(shù)是size次撮竿，樹實(shí)現(xiàn)的兩個(gè)方法的時(shí)間復(fù)雜度都為O(h),執(zhí)行兩個(gè)方法的整體速度要好于數(shù)組實(shí)現(xiàn)技掏。
執(zhí)行結(jié)果：
將size和調(diào)用次數(shù)m都賦值為100000時(shí)掉丽，樹實(shí)現(xiàn)的整體速度就會下降悯搔，因?yàn)閟ize越大佃蚜，樹的深度越大夭咬，兩個(gè)O(h)的復(fù)雜度使得整體效率變差趋箩。
3.總結(jié)
這篇介紹了并查集的概述和兩種實(shí)現(xiàn)方法赃额，雖然當(dāng)操作數(shù)變大時(shí)，樹實(shí)現(xiàn)的并查集會相應(yīng)變慢叫确，但常用的還是第二種方法跳芳，用樹來實(shí)現(xiàn)并查集，其實(shí)用樹來實(shí)現(xiàn)并查集還有一些優(yōu)化方法竹勉，能夠使其速度遠(yuǎn)大于用數(shù)組實(shí)現(xiàn)的速度飞盆。
下一篇將會介紹幾種優(yōu)化并查集的方法。
