1、并查集的初始化

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

int father[N];

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

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

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

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

2、并查集的查找操作

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

遞推代碼：

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

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

遞歸代碼：

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

3、并查集的合并操作

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

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

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

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

4、為什么要路徑壓縮？

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

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

比如下面這張圖：

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

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

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

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

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

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

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

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

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

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

總結

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

最新評論