等價(jià)類與并查集的原理和應(yīng)用

?????? 并查集主要解決判斷兩個(gè)元素是否同屬一個(gè)集合，和把兩個(gè)不屬同一集合的兩個(gè)元素進(jìn)行合并的問題。 ( 想想最小生成樹中的 kruskal 算法 : 關(guān)鍵是判別兩個(gè)節(jié)點(diǎn)是否屬同一連通分量，這里并查集可以以很好的時(shí)間復(fù)雜度解決它，幾乎是線性時(shí)間！！ )

?????? 首先要知道關(guān)于等價(jià)類（就相當(dāng)于前面說的同屬一個(gè)集合）的基本性質(zhì)。

?????? 等價(jià)類三大性質(zhì)：（用Ｘ o Ｙ表Ｘ與Ｙ等價(jià)）

?????? 自反性：如Ｘ o Ｘ則Ｘ o Ｘ；

?????? 對(duì)稱性：如Ｘ o Ｙ則Ｙ o Ｘ；

?????? 傳遞性：如Ｘ o Ｙ且Ｙ o Ｚ則Ｘ o Ｚ；

等價(jià)類應(yīng)用：

?????? 設(shè)初始有一集合 s={0,1,2,3,4,5,6,7,8,9,10,11}

?????? 依次讀若干事先定義的等價(jià)對(duì)

???0o 4,3o 1,6o 10,8o 9, 7o 4, 6o 8,3o 5,2o 11,11o 0.

??? 我們想把每次讀入一個(gè)等價(jià)對(duì)后，把等價(jià)集合合并起來。

??? 則每讀入一個(gè)等價(jià)對(duì)后的集合狀態(tài)是：（用｛｝表示一個(gè)等價(jià)集合）

初始 ????? {0},{1},{2},{3},{4},{5},{6},{7},{8},{9},{10},{11}

0 o 4 ???? {0,4},{1},{2},{3},{5},{6},{7},{8},{9},{10},{11}

3 o 1 ???? {0,4}, {1,3},{2},{5},{6},{7},{8},{9},{10},{11}

6 o 10??? { 0,4},{1,3},{2},{5},{6,10},{7},{8},{9},{11}

8 o 9 ??? ? {0,4},{1,3},{2},{5},{6,10},{7},{8,9},{11}

7 o 4 ???? {0,4,7},{1,3},{2},{5},{6,10},{8,9},{11}

6 o 8 ??? ? {0,4,7},{1,3},{2},{5},{6,8,9,10},{11}

3 o 5 ??? ? {0,4,7},{1,3,5},{2},{6,8,9,10},{11}

2 o 11????{ 0,4,7},{1,3,5},{2,11},{6,8,9,10}

11 o 0????{ 0,2,4,7,11},{1,3,5},{6,8,9,10}

?????? 怎樣來實(shí)現(xiàn)這樣的結(jié)構(gòu)呢？

?????? 我們可建一個(gè)含Ｓ元素個(gè)數(shù)大小的指針數(shù)組 node *seq[N] 。其中每個(gè)元素是一個(gè)指向其下一個(gè)等價(jià)元素對(duì)應(yīng)序號(hào)節(jié)點(diǎn)的頭指針。每讀入一個(gè)等價(jià)對(duì)后，修改鏈表。上例讀完后的表狀態(tài)是：

建表算法如下：
void creatlist()
{?int x,y,c;
?node *P;
?scanf("%d",&c);?//讀入等價(jià)對(duì)數(shù)
?for(int i=0;i<c;i++)
?{
??scanf("%d %d",&x,&y);
??P=new node;?
??P->data=y;
??P->next=seq[x];
??seq[x]=P;
??P=new node;?//為什么要兩個(gè)節(jié)點(diǎn)呢？因?yàn)槟憬藗€(gè)Ａ的下一等價(jià)對(duì)Ｂ那么由對(duì)稱性，應(yīng)該再建一個(gè)節(jié)點(diǎn)表示Ｂ的下一等價(jià)對(duì)是Ａ。
??P->data=x;
??P->next=seq[y];
??seq[y]=P;
?}//for
}

?

??? 現(xiàn)在我們想把同屬一個(gè)等價(jià)集合的元素分別輸出出來。有什么辦法呢？

?????? 先看圖。Ｓｅｑ［０］它有兩個(gè)等價(jià)類１１，４。這樣直接輸出０，１１，４。是否可行呢？答案是不行的，你看下４結(jié)點(diǎn)還有兩個(gè)等價(jià)類７，０。當(dāng)然已知０，４是等價(jià)的了，

但７你是忽略的了（因?yàn)閭鬟f性：０，４等價(jià)且４，７等價(jià)就必然有０，７等價(jià)。所以７也應(yīng)該被輸出）。還有 11 節(jié)點(diǎn)下的２你也沒算……

?????? 我們可以采用類似ＤＦＳ（深度優(yōu)先搜索）的策略對(duì)每個(gè)集合的元素進(jìn)行遍歷。例如：

開始從０節(jié)點(diǎn)搜起，把它下面的兩個(gè)直接等價(jià)類入棧，然后依次出棧，每次出棧后對(duì)出棧元素的直接等價(jià)類再進(jìn)行一次類似的ＤＦＳ，直到包含０節(jié)點(diǎn)的等價(jià)集合被全部輸出。程序如下：

void display()
{?
?stack<int> S;
?int t;node *p;
?for(int i=0;i<N;i++)
?{
??if(!outed[i])??//是否輸出過的標(biāo)記
??{
??? cout<<"new class"<<'{';
??? S.push(i);
??? cout<<i<<' ';
??? outed[i]=1;
??? while(!S.empty())
??? {
??? t=S.top();
??? S.pop();
?? ?p=seq[t];
??? while(p!=NULL)
?? ?{
???? if(!outed[p->data])
??? ?{
??? ??cout<<p->data<<' ';
??? ??S.push(p->data);
??? ??outed[p->data]=1;
??? ?}
??? ?p=p->next;
?? ?}//while
???}//while
??? cout<<'}'<<endl;
??}//if
?}//for
}

其實(shí)有比這個(gè)方便快速的數(shù)據(jù)結(jié)構(gòu)來實(shí)現(xiàn)這個(gè)問題，那就是并查集。

并查集對(duì)這個(gè)問題的處理思想是開始把每一個(gè)對(duì)象看作是一個(gè)單元素集合，然后依次按順序（就是讀入等價(jià)對(duì)）將屬于同一等價(jià)類的元素所在的集合合并。在此過程中將重復(fù)地使用一個(gè)搜索運(yùn)算，確定一個(gè)元素在哪一個(gè)集合中。當(dāng)讀入一個(gè)等價(jià)對(duì)ＡＢ時(shí)，先檢測這兩個(gè)等價(jià)對(duì)是否同屬一個(gè)集合，如是，則不用合并。不是，則用個(gè)合并算法把這兩個(gè)包含ＡＢ的集合合并，使兩個(gè)集合的任兩個(gè)元素都是等價(jià)的（由傳遞性）。

?????? 為了方便，我們通常用一個(gè)集合的根結(jié)點(diǎn)序號(hào)來表示這個(gè)集合。

來看下具體結(jié)構(gòu)實(shí)現(xiàn)：

定義個(gè)Ｐａｒｅｎｔ［Ｎ］的數(shù)組，作為結(jié)構(gòu)。Ｐａｒｅｎｔ中存的就是序號(hào)結(jié)點(diǎn)的父親結(jié)點(diǎn)的序號(hào)，例：如果Ｐａｒｅｎｔ［３］＝４就是說３號(hào)結(jié)點(diǎn)的雙親是４號(hào)結(jié)點(diǎn)。如果一個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)是負(fù)數(shù)的話，我們就認(rèn)為它是一個(gè)集合的根結(jié)點(diǎn)，因?yàn)閿?shù)組中沒有序號(hào)是負(fù)的。并且用負(fù)的絕對(duì)值作為這個(gè)集合中所含節(jié)點(diǎn)個(gè)數(shù)，如： parent[6]=-4; 說明６號(hào)節(jié)點(diǎn)是個(gè)集合根結(jié)點(diǎn)，這個(gè)集合有４個(gè)元素。初始時(shí)，所有Ｐａｒｅｎｔ賦為 -1 ，說明每個(gè)結(jié)點(diǎn)都是根結(jié)點(diǎn)（Ｎ個(gè)獨(dú)立節(jié)點(diǎn)集合），只包含一個(gè)元素（就是自己了）。

?????? 實(shí)現(xiàn)這個(gè)數(shù)據(jù)結(jié)構(gòu)主要有三個(gè)函數(shù)：如下：

void UFset()??//初始化
{
?for(int i=0;i<N;i++)
??parent[i]=-1;
}

?

int Find(int x)??//返回第Ｘ節(jié)點(diǎn)所屬集合的根結(jié)點(diǎn)
{
?for(int i=x;parent[i]>=0;i=parent[i]);
?while(i!=x)???//優(yōu)化方案――壓縮路徑
?{
??int tmp=parent[x];
??parent[x]=i;
???? x=tmp;
?}
?return i;
}

?

void Union(int R1,int R2)??//將兩個(gè)不同集合的元素進(jìn)行合并，使兩個(gè)集合中任兩個(gè)元素都連通
{
?int tmp=parent[R1]+parent[R2];
?if(parent[R1]>parent[R2])?//優(yōu)化方案――加權(quán)法則
?{
??parent[R1]=R2;
??parent[R2]=tmp;
?}
?else
?{
??parent[R2]=R1;
??parent[R1]=tmp;
?}
}

在Ｆｉｎｄ函數(shù)中如果僅僅靠一個(gè)循環(huán)來直接得到節(jié)點(diǎn)的所屬集合根結(jié)點(diǎn)的話。通過多次的Ｕｎｉｏｎ操作就會(huì)有很多節(jié)點(diǎn)在樹的比較深層次中，再Ｆｉｎｄ起來就會(huì)很費(fèi)時(shí)。通過加一個(gè)Ｗｈｉｌｅ循環(huán)（壓縮路徑）每次都把從 i 到集合根結(jié)點(diǎn)的路過結(jié)點(diǎn)的雙親直接設(shè)為集合的根結(jié)點(diǎn)。雖然這增加了時(shí)間，但以后的Ｆｉｎｄ會(huì)快。平均效能而言，這是個(gè)高效方法。

兩個(gè)集合并時(shí)，任一方可做為另一方的孩子。怎樣來處理呢，現(xiàn)在一般采用加權(quán)合并，把兩個(gè)集合中元素個(gè)數(shù)少的做為個(gè)數(shù)多的孩子。有什么優(yōu)勢呢？直觀上看，可以減少集合樹的深層元素的個(gè)數(shù)，減少Ｆｉｎｄ時(shí)間。

如從０開始到Ｎ不斷合并 i 和 i+1 結(jié)點(diǎn)會(huì)怎樣呢？

這樣Ｆｉｎｄ任一節(jié)點(diǎn)所屬集合的時(shí)間復(fù)雜度幾乎都是Ｏ (1) ！！

不用加權(quán)規(guī)則就會(huì)得到

這就是典型的退化樹現(xiàn)象，再Ｆｉｎｄ起來就會(huì)很費(fèi)時(shí)（如找Ｎ－１節(jié)點(diǎn)看看）。

以下是讀入等價(jià)對(duì)后的 parent[N] 查找合并過程狀態(tài)：

再說一個(gè)并查集應(yīng)用最完美的地方：最小生成樹的 kruskal 算法：

算法基本思想是：

開始把所有節(jié)點(diǎn)作為各自的一個(gè)單獨(dú)集合，以為每次從邊信息中得到一個(gè)最短的邊，如果這個(gè)邊鄰接了兩個(gè)不同集合的節(jié)點(diǎn)，就把這兩個(gè)節(jié)點(diǎn)的所屬集合結(jié)合起來，否則繼續(xù)搜索。直至所有節(jié)點(diǎn)都同屬一個(gè)集合，就生成了一個(gè)最小生成樹。int kruskal(int parent[],int N)
{
?int i,j,k,x,y;
?int min;
?while(k<=N-1)?//產(chǎn)生Ｎ－１條邊
?{
??min=MAX_INT;
??for(i=1;i<=N;i++)?
???for(j=1;j<=N;j++)
???{
????if(sign[i][j]==0&&i!=j) //sign[N][N]是標(biāo)志節(jié)點(diǎn)是否被訪問過或已被排除……
????{
?????if(arcs[i][j]<min)　//arcs[N][N]存放邊的長度
?????{
??????min=arcs[i][j];
??????x=i;
??????y=j;
?????}//if
????}//if
???}//for
??if(Find(parent,x)==Find(parent,y))?//如Ｘ，Ｙ已經(jīng)屬同一連通分量，則不合并，排除……
???sign[x][y]=1;
??else
???{
??? Union(parent,x,y);
??? Sign[x][y]=1;
?? }
?k++;
?}//while
}