考研資料結構之並查集

語言: CN / TW / HK

theme: healer-readable

小知識,大挑戰!本文正在參與“程式設計師必備小知識”創作活動

image.png 漏網之魚:邏輯結構——“集合”

邏輯結構——資料元素之間的邏輯關係是什麼?

集合的兩個基本操作——“並”和“查”

Find ——“查”操作:確定一個指定元 素所屬集合 Union ——“並”操作:將兩個不想交 的集合合併為一個 注:並查集(Disjoint Set)是邏輯結 構——集合的一種具體實現,只進行 “並”和“查”兩種基本操作

image.png

image.png

image.png

image.png 如何“查”到一個元素到底屬於哪一個集合? —— 從指定元素出發,一路向北,找到根節點 如何判斷兩個元素是否屬於同一個集合? —— 分別查到兩個元素的根,判斷根節點是否相同即可 ```c++

include

using namespace std;

define SIZE 13

int UFSets[SIZE]; //集合元素組

//初始化並查集 void Initial(int S[]){ for(int i=0;i<SIZE;i++) S[i]=-1; }

//Find "查"操作,找X所屬集合(返回X所屬根結點) int Find(int S[],int X){ while(S[X]>=0) //迴圈尋找X的根 X=S[X]; return X; }

//Union "並"操作,講兩個集合合併為一個 void Union(int S[],int Root1,int Root2){ //要求Root1與Root2是不同集合

if(Root1==Root2)    return;

//將根Root2連線到另一根Root1下面

S[Root2]=Root1;

}

//Union "並"操作,小樹合併到大樹 void Union1(int S[],int Root1,int Root2){ if(Root1==Root2) return; if(S[Root2]>S[Root1]){ S[Root1]+=S[Root2]; S[Root2]=Root1; //小樹合併到大樹 }else{ S[Root2]+=S[Root1]; S[Root1]=Root2;

}

}

//用並查集判斷一個圖有幾個連通分量(圖用鄰接矩陣表示) int ComponentCount(int g[5][5]){ //g[5][5]是一個二維陣列表示的鄰接矩陣 int S[5]; for(int i=0;i<5;i++) S[i]=-1; //定義,初始化並查集

 for(int i=0;i<5;i++)
    for(int j=i+1;j<5;j++)
     if(g[i][j]>0){

        int iRoot=Find(S,i);    
        int jRoot=Find(S,j);
        if(iRoot!=jRoot)
            Union1(S,iRoot,jRoot);

    }


int count=0;
for(int i=0;i<5;i++)
    if(S[i]<0)  count++;
    return count;

}

//用並查集判斷一個圖是否有環(圖用鄰接矩陣表示) int hasAcyclic(int g[5][5]){ //g[5][5]是一個二維陣列表示的鄰接矩陣 int S[5]; //初始化並查集 for(int i=0;i<5;i++) S[i]=-1; for(int i=0;i<5;i++) for(int j=i+1;j<5;j++) if(g[i][j]>0){ int iRoot=Find(S,i); int jRoot=Find(S,j); if(iRoot!=jRoot) Union(S,iRoot,jRoot); else return 1;//在一個連通子圖中,但凡再多一條邊,必有環 } return 0;//圖中沒環
}

int main(){

return 0;

} ```