C++并查集算法簡單詳解
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é)點。
總結(jié)
到此這篇關(guān)于C++并查集算法簡單詳解的文章就介紹到這了,更多相關(guān)C++并查集算法內(nèi)容請搜索腳本之家以前的文章或繼續(xù)瀏覽下面的相關(guān)文章希望大家以后多多支持腳本之家!
相關(guān)文章
- C++學了這么多年你知道為什么定義類時,類的定義放在.h文件中,而類的實現(xiàn)放在cpp文件中。它們?yōu)槭裁茨軌蜿P(guān)聯(lián)到一起呢?你知道什么東西可以放在.h文件中,什么不能。什么東西又可以放在cpp文件中。如果你忘記了或是壓根就不明白,那么讀過此文你會清晰無比?。?/div> 2014-09-09
淺談C++的語句語法與強制數(shù)據(jù)類型轉(zhuǎn)換
這篇文章主要介紹了淺談C++的語句語法與強制數(shù)據(jù)類型轉(zhuǎn)換,是C++入門學習中的基礎(chǔ)知識,需要的朋友可以參考下2015-09-09VTK8.1?在?Qt5.9?環(huán)境下的配置編譯和安裝過程
為了實現(xiàn)realsense的PCL點云顯示,需要VTK支持。由于整個平臺在Qt環(huán)境實現(xiàn),VTK編譯為Qt插件。整個過程并不復(fù)雜,網(wǎng)上的文章大多不全,自己梳理了一下,分享出來,需要的朋友可以參考下2022-07-07STL區(qū)間成員函數(shù)及區(qū)間算法總結(jié)
這篇文章主要匯總介紹了STL區(qū)間成員函數(shù)及區(qū)間算法,有需要的小伙伴可以參考下。2015-07-07最新評論