C++如何實現(xiàn)并查集算法

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

1、并查集的初始化

并查集是用一個數(shù)組實現(xiàn)的。首先先定義一個數(shù)組：

int father[N];

father[i]表示元素i的父親結(jié)點。

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

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

 這樣，就將father數(shù)組初始化完畢。

2、并查集的查找操作

由于規(guī)定同一個集合中只存在一個根結(jié)點，因此查找操作，就是查找給定結(jié)點的根結(jié)點的過程。可以通過遞推或遞歸來實現(xiàn)，思路都是一樣的，都是反復(fù)尋找父親結(jié)點，直到找到根結(jié)點為止。

遞推代碼：

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

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

遞歸代碼：

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

3、并查集的合并操作

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

合并操作的代碼實現(xiàn)：(假設(shè)有兩個集合，一個集合里有元素a，一個集合有元素b)

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

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

4、為什么要路徑壓縮？

5、實現(xiàn)路徑壓縮

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

比如下面這張圖：

觀察圖不難發(fā)現(xiàn)，上圖中father[1] = 1，father[2] = 1，father[3] = 2，father[4] = 3。經(jīng)過路徑壓縮，就變成下面這幅圖：

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

如何用代碼實現(xiàn)路徑壓縮呢？以下是具體代碼：

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

 以上代碼，實現(xiàn)了在查詢獲取根結(jié)點的同時，將路徑進行壓縮優(yōu)化，代碼雖然很短，但是很巧妙，下面解釋下上述代碼：

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

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

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

這樣就實現(xiàn)了路徑壓縮，即將結(jié)點的父親直接指向根結(jié)點。

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

感謝你能夠認真閱讀完這篇文章，希望小編分享的“C++如何實現(xiàn)并查集算法”這篇文章對大家有幫助，同時也希望大家多多支持億速云，關(guān)注億速云行業(yè)資訊頻道，更多相關(guān)知識等著你來學習!