并查集，在一些有N個(gè)元素的集合應(yīng)用問題中，我們通常是在開始時(shí)讓每個(gè)元素構(gòu)成一個(gè)單元素的集合，然后按一定順序?qū)儆谕唤M的元素所在的集合合并，其間要反復(fù)查找一個(gè)元素在哪個(gè)集合中。這一類問題近幾年來反復(fù)出現(xiàn)在信息學(xué)的國際國內(nèi)賽題中，其特點(diǎn)是看似并不復(fù)雜，但數(shù)據(jù)量極大，若用正常的數(shù)據(jù)結(jié)構(gòu)來描述的話，往往在空間上過大，計(jì)算機(jī)無法承受；即使在空間上勉強(qiáng)通過，運(yùn)行的時(shí)間復(fù)雜度也極高，根本就不可能在比賽規(guī)定的運(yùn)行時(shí)間（1～3秒）內(nèi)計(jì)算出試題需要的結(jié)果，只能用并查集來描述。
首先我們給出并查集（union-find）的api：
在《algorithm》書中，對與uf的應(yīng)用直接給出了代碼，但是其中find和union方法并沒有直接實(shí)現(xiàn)，而是空著的。書中代碼如下：
注意：這里看見有一個(gè)StdIn的類作為類似于輸入流的作用，這個(gè)在java中是不存在的，這是這本書自己構(gòu)造的一個(gè)類。相信以后在這本書中也會有類似的部分，可以在網(wǎng)上找到其中的具體實(shí)施代碼，我會發(fā)送出來的。
為什么不直接實(shí)現(xiàn)find和union方法呢，這里會考慮到數(shù)據(jù)結(jié)構(gòu)和算法復(fù)雜度的問題。
我們將其分為：quickunion，quickfind，weightedquickunion，weightedquickunion with path compression；
1）Quick-Find
其中判斷p和q兩個(gè)元素是否連接便是讓兩個(gè)元素的id[]相同。
此時(shí)，find（）便是直接返回id[p]的值
而union（）便是將連接的兩個(gè)集合的id[]變?yōu)橐恢拢寒?dāng)然，我們首先要判斷她們是不是已經(jīng)連接；
由上圖便可看出，我們union（3，4），得到兩者的id[]相同，即id[3]=id[4]=3（id值為連接的集合包含的任意一個(gè)數(shù)）；
得到的代碼如下：
package unionFind;
public class QuickFindUF {
private int id[];
private int count;
public QuickFindUF(int N){
count=N;
id=new int[N];
for(int i=0;i<N;i++){
id[i]=i;
}
}
public int count(){
return count;
}
public boolean connected(int p,int q){
return find(p)==find(q);
}
public int find(int p){
return id[p];
}
public void union(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;
}
count--;
}
}
2)Quick-Union
Quick-Union的結(jié)構(gòu)如下圖所示：
即每一個(gè)結(jié)點(diǎn)的id為上一個(gè)結(jié)點(diǎn)。而根節(jié)點(diǎn)便是root=id[root]；
判斷兩個(gè)元素是否連接則是判斷兩個(gè)元素的根（root）是否相同。
find（）則為找到元素的根節(jié)點(diǎn)；
union（p，q）即將p的根節(jié)點(diǎn)與q的根節(jié)點(diǎn)連接。
代碼實(shí)現(xiàn)如下：
package unionFind;
public class QuickUnionUF {
private int id[];
private int count;
public QuickUnionUF(int N){
id=new int[N];
count=N;
for(int i=0;i<N;i++){
id[i]=i;
}
}
public int count(){
return count;
}
public int find(int i){
while(i!=id[i]){
i=id[i];
}
return i;
}
public void union(int p,int q){
if(find(p)==find(q))return;
id[find(p)]=find(q);
count--;
}
public boolean connected(int p,int q){
return find(p)==find(q);
}
}
3）Weighted Quick-Union
當(dāng)然，我們?nèi)绻鷣y的將根節(jié)點(diǎn)相互連接，會導(dǎo)致這個(gè)樹的結(jié)構(gòu)非常糟糕，比如：
我們可以看到這個(gè)樹的結(jié)構(gòu)非常非常糟糕。
為了避免這個(gè)情況，我們記錄樹的大小，并且總是將小的樹連接到大的樹：
使用這種方法可以很大程度的優(yōu)化樹的結(jié)構(gòu)，例如上圖的樹我們可以變?yōu)椋?/p>
具體實(shí)現(xiàn)代碼如下：
package unionFind;
public class WeightedQuickUnionUF {
private int id[];
private int count;
private int sz[];
public WeightedQuickUnionUF(int N){
count=N;
id=new int[N];
sz=new int[N];
for(int i=0;i<N;i++){
id[i]=i;
sz[i]=1;
}
}
public int find(int p){
while(p!=id[p])p=id[p];
return p;
}
public void union(int p,int q){
int pid=find(p);
int qid=find(q);
if(qid==pid)return ;
if(sz[pid]<sz[qid]){
id[pid]=qid;
sz[qid]+=sz[pid];
} else{
id[qid]=pid;
sz[pid]+=sz[qid];
}
count--;
}
public int count(){
return count;
}
public boolean connected(int p,int q){
return find(p)==find(q);
}
}
4）Weighted Quick-Union with Path Compression
最優(yōu)情況下，我們希望所有的節(jié)點(diǎn)都直接連接到根節(jié)點(diǎn)上，但是又不希望像QuickUnion那樣大量修改連接，這時(shí)，我們可以在檢查節(jié)點(diǎn)的同時(shí)將它與根節(jié)點(diǎn)直接連接。
例如，我們對下列并查集進(jìn)行union（7，3）；
在采取最優(yōu)算法下，結(jié)果如下：
可以看出，我們將遍歷到的節(jié)點(diǎn)都直接與根節(jié)點(diǎn)直接連接，這一切只需要在find內(nèi)的循環(huán)進(jìn)行修改就可以實(shí)現(xiàn)。
具體的代碼如下：
package unionFind;
public class WeightedQuickUnionUFWPC {
private int id[];
private int count;
private int sz[];
public WeightedQuickUnionUFWPC(int N){
count=N;
id=new int[N];
sz=new int[N];
for(int i=0;i<N;i++){
id[i]=i;
sz[i]=1;
}
}
public int find(int p){
int root=p;
while(root!=id[root])root=id[root];
while(p!=root){
int x=p;
id[x]=root;
p=id[p];
}
return root;
}
public void union(int p,int q){
int pid=find(p);
int qid=find(q);
if(qid==pid)return ;
if(sz[pid]<sz[qid]){
id[pid]=qid;
sz[qid]+=sz[pid];
} else{
id[qid]=pid;
sz[pid]+=sz[qid];
}
count--;
}
public int count(){
return count;
}
public boolean connected(int p,int q){
return find(p)==find(q);
}
}
這四種方法能夠適應(yīng)不同的情況，但是對于算法復(fù)雜度來說，這四種方法就會有很大的差別：
對于每一項(xiàng)的得出，《algorithm》給出了很詳細(xì)的解釋，我希望自己能夠有時(shí)間寫一篇文章來細(xì)講一下。（別說了。感覺還有好多坑沒填）
轉(zhuǎn)載出處：https://www.cnblogs.com/DSNFZ/articles/7623522.html
