1、并查集的初始化

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

int father[N];

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

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

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

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

2、并查集的查找操作

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

遞推代碼：

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

上述代碼中， while(x != father[x])，說明當(dāng)x的父親結(jié)點(diǎn)不等于本身時(shí)，也就是x不是根結(jié)點(diǎn)時(shí)就繼續(xù)循環(huán)，因?yàn)楦赣H結(jié)點(diǎn)等于本身這個(gè)情況，只有在根結(jié)點(diǎn)才會(huì)出現(xiàn)。

遞歸代碼：

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

3、并查集的合并操作

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

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

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

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

4、為什么要路徑壓縮？

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

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

比如下面這張圖：

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

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

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

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

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

 if(father[x] != x)，當(dāng)所查找的元素x的父親結(jié)點(diǎn)不是自己，也就是x不是根結(jié)點(diǎn)時(shí)，

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

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

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

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

總結(jié)

到此這篇關(guān)于C++并查集算法簡(jiǎn)單詳解的文章就介紹到這了,更多相關(guān)C++并查集算法內(nèi)容請(qǐng)搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家！

最新評(píng)論