C++並查集算法簡單詳解

Posted on by

1、並查集的初始化

並查集是用一個數組實現的。首先先定義一個數組：

int father[N];

father[i]表示元素i的父親結點。

接下來進行初始化。一開始，每個元素都分別是獨立的一個集合，父親結點就是它自己，所以初始化時將所有father[i]等於i：

for(int i = 1; i <= N; i++){
    father[i] = i;
}

 這樣，就將father數組初始化完畢。

2、並查集的查找操作

由於規定同一個集合中隻存在一個根結點，因此查找操作，就是查找給定結點的根結點的過程。可以通過遞推或遞歸來實現，思路都是一樣的，都是反復尋找父親結點，直到找到根結點為止。

遞推代碼：

//findFather函數返回元素x所在集合的根結點
int findFather(int x){
    while(x != father[x]){    //如果不是根結點，繼續循環
        x = father[x];    //獲得自己的父親結點
    }
    return x;
}

上述代碼中， while(x != father[x])，說明當x的父親結點不等於本身時，也就是x不是根結點時就繼續循環，因為父親結點等於本身這個情況，隻有在根結點才會出現。

遞歸代碼：

int findFather(int x){
    if(x == father[x]) return x;    //如找到根結點，就返回根結點編號x
    else return findFather(father[x]); //否則，遞歸判斷x的父親結點是否是根結點
}

3、並查集的合並操作

合並，就是把兩個集合合並成一個集合。實現過程是：先判斷兩個元素是否屬於同一個集合，不屬於同一個集合，就開始進行合並操作。判斷兩個元素是否屬於同一個集合的具體思路，就是調用上面的findFather函數，分別查找兩個元素所屬集合的根結點，根結點不同，則兩個元素不屬於同一個集合。合並兩個集合的具體思路，就是將其中一個集合的根結點的父親指向另外一個集合的根結點即可。

合並操作的代碼實現：(假設有兩個集合，一個集合裡有元素a，一個集合有元素b)

void Union(int a, int b){
    //讓一個集合的根結點的父親指向另一個集合的根結點
    father(findFather(a)) = findFather(b); 
}

註意，合並操作之前，最好先判斷下待合並的兩個元素是否位於同一個集合。

4、為什麼要路徑壓縮？

5、實現路徑壓縮

由於findFather函數目的就是查找根結點，所以，我們在查找結點的路徑上直接將所有結點的父親都指向根結點，查找的時候就不必一直回溯去尋找父親瞭，查詢的復雜度可以降為O(1)。

比如下面這張圖：

觀察圖不難發現，上圖中father[1] = 1，father[2] = 1，father[3] = 2，father[4] = 3。經過路徑壓縮，就變成下面這幅圖：

相當於將所有結點的父親都直接指向根結點，這就是路徑壓縮。

如何用代碼實現路徑壓縮呢？以下是具體代碼：

int findFather(int x){
    if(father[x] != x) father[x] = findFather(father[x]);
    return father[x];
}

 以上代碼，實現瞭在查詢獲取根結點的同時，將路徑進行壓縮優化，代碼雖然很短，但是很巧妙，下面解釋下上述代碼：

 if(father[x] != x)，當所查找的元素x的父親結點不是自己，也就是x不是根結點時，

findFather(father[x])，就繼續遞歸查找父結點，直到找到根結點為止，

father[x] = findFather(father[x])，然後將找到的根結點直接賦給x的父親結點。

這樣就實現瞭路徑壓縮，即將結點的父親直接指向根結點。

return father[x]，返回查找到的根結點。

總結

到此這篇關於C++並查集算法簡單詳解的文章就介紹到這瞭,更多相關C++並查集算法內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！

推薦閱讀：