等價(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à)集合合并起來(lái)。
???
則每讀入一個(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}
??????
怎樣來(lái)實(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à)集合的元素分別輸出出來(lái)。有什么辦法呢？
??????
先看圖。Ｓｅｑ［０］它有兩個(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)來(lái)實(shí)現(xiàn)這個(gè)問題，那就是并查集。
并查集對(duì)這個(gè)問題的處理思想是開始把每一個(gè)對(duì)象看作是一個(gè)單元素集合，然后依次按順序（就是讀入等價(jià)對(duì)）將屬于同一等價(jià)類的元素所在的集合合并。在此過程中將重復(fù)地使用一個(gè)搜索運(yùn)算，確定一個(gè)元素在哪一個(gè)集合中。當(dāng)讀入一個(gè)等價(jià)對(duì)ＡＢ時(shí)，先檢測(cè)這兩個(gè)等價(jià)對(duì)是否同屬一個(gè)集合，如是，則不用合并。不是，則用個(gè)合并算法把這兩個(gè)包含ＡＢ的集合合并，使兩個(gè)集合的任兩個(gè)元素都是等價(jià)的（由傳遞性）。
??????
為了方便，我們通常用一個(gè)集合的根結(jié)點(diǎn)序號(hào)來(lái)表示這個(gè)集合。
來(lái)看下具體結(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)來(lái)直接得到節(jié)點(diǎn)的所屬集合根結(jié)點(diǎn)的話。通過多次的Ｕｎｉｏｎ操作就會(huì)有很多節(jié)點(diǎn)在樹的比較深層次中，再Ｆｉｎｄ起來(lái)就會(huì)很費(fèi)時(shí)。通過加一個(gè)Ｗｈｉｌｅ循環(huán)（壓縮路徑）每次都把從
i
到集合根結(jié)點(diǎn)的路過結(jié)點(diǎn)的雙親直接設(shè)為集合的根結(jié)點(diǎn)。雖然這增加了時(shí)間，但以后的Ｆｉｎｄ會(huì)快。平均效能而言，這是個(gè)高效方法。
兩個(gè)集合并時(shí)，任一方可做為另一方的孩子。怎樣來(lái)處理呢，現(xiàn)在一般采用加權(quán)合并，把兩個(gè)集合中元素個(gè)數(shù)少的做為個(gè)數(shù)多的孩子。有什么優(yōu)勢(shì)呢？直觀上看，可以減少集合樹的深層元素的個(gè)數(shù)，減少Ｆｉｎｄ時(shí)間。
如從０開始到Ｎ不斷合并
i
和
i+1
結(jié)點(diǎn)會(huì)怎樣呢？
這樣Ｆｉｎｄ任一節(jié)點(diǎn)所屬集合的時(shí)間復(fù)雜度幾乎都是Ｏ
(1)
?。?/span>
不用加權(quán)規(guī)則就會(huì)得到
這就是典型的退化樹現(xiàn)象，再Ｆｉｎｄ起來(lái)就會(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é)合起來(lái)，否則繼續(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]存放邊的長(zhǎng)度
?????{
??????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
}