C++如何實現并查集算法

這篇文章主要介紹了C++如何實現并查集算法，具有一定借鑒價值，感興趣的朋友可以參考下，希望大家閱讀完這篇文章之后大有收獲，下面讓小編帶著大家一起了解一下。

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++如何實現并查集算法”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關注億速云行業資訊頻道，更多相關知識等著你來學習!