C++并查集怎么實(shí)現(xiàn)-創(chuàng)新互聯(lián)

這篇文章主要介紹“C++并查集怎么實(shí)現(xiàn)”，在日常操作中，相信很多人在C++并查集怎么實(shí)現(xiàn)問題上存在疑惑，小編查閱了各式資料，整理出簡(jiǎn)單好用的操作方法，希望對(duì)大家解答”C++并查集怎么實(shí)現(xiàn)”的疑惑有所幫助！接下來，請(qǐng)跟著小編一起來學(xué)習(xí)吧！

專注于為中小企業(yè)提供成都網(wǎng)站制作、網(wǎng)站建設(shè)服務(wù),電腦端+手機(jī)端+微信端的三站合一,更高效的管理,為中小企業(yè)六安免費(fèi)做網(wǎng)站提供優(yōu)質(zhì)的服務(wù)。我們立足成都，凝聚了一批互聯(lián)網(wǎng)行業(yè)人才，有力地推動(dòng)了上千余家企業(yè)的穩(wěn)健成長(zhǎng)，幫助中小企業(yè)通過網(wǎng)站建設(shè)實(shí)現(xiàn)規(guī)模擴(kuò)充和轉(zhuǎn)變。

并查集 是一種樹型的數(shù)據(jù)結(jié)構(gòu),用于處理一些不相加集合的合并和查詢問題。在使用中常常以森林來表示。 并查集也是用來維護(hù)集合的,和前面學(xué)習(xí)的set不同之處在于,并查集能很方便地同時(shí)維護(hù)很多集合。如果用set來維護(hù)會(huì)非常的麻煩。并查集的核心思想是記錄每個(gè)結(jié)點(diǎn)的父親結(jié)點(diǎn)是哪個(gè)結(jié)點(diǎn)。

前言

并查集是一種多叉樹，用于處理不相交的集合的合并與查詢問題（判斷）。

通俗理解：在日常生活中，我們會(huì)因?yàn)槟硞€(gè)人是自己的朋友，哪怕是朋友的朋友也是有朋友，會(huì)給予通融、 偏袒。而并查集的基本概念，就是判斷某兩個(gè)集合是否是“朋友”關(guān)系，并讓兩個(gè)集合成為“朋友”

常用操作

初始化：每個(gè)結(jié)點(diǎn)單獨(dú)作為一個(gè)集合

查詢：求元素所在的集合的代表元素，即根結(jié)點(diǎn)

合并：將兩個(gè)元素所在的集合，合并為一個(gè)集合

合并之前，應(yīng)先判斷兩個(gè)元素是否屬于同一集合，用上面的“查詢”來實(shí)現(xiàn)

算法實(shí)現(xiàn)

初始化:初始的時(shí)候每個(gè)結(jié)點(diǎn)各自為一個(gè)集合,father[i]表示結(jié)點(diǎn) i 的父親結(jié)點(diǎn),如果 father[i]=i,我們認(rèn)為這個(gè)結(jié)點(diǎn)是當(dāng)前集合根結(jié)點(diǎn)（開始時(shí)每個(gè)節(jié)點(diǎn)根節(jié)點(diǎn)是他自己）。

void init() {

    for (int i = 1; i <= n; ++i) {

        father[i] = i;

    }

}

查找:查找結(jié)點(diǎn)所在集合的根結(jié)點(diǎn),結(jié)點(diǎn) x 的根結(jié)點(diǎn)必然也是其父親結(jié)點(diǎn)的根結(jié)點(diǎn)（像是有遞歸的樣子）。

int get(int x) {

    if (father[x] == x) { // x 結(jié)點(diǎn)就是根結(jié)點(diǎn)

        return x; 

    }

    return get(father[x]); // 如果該節(jié)點(diǎn)不是根節(jié)點(diǎn)，繼續(xù)尋找父結(jié)點(diǎn)的根結(jié)點(diǎn)

}

合并:將兩個(gè)元素所在的集合合并在一起,通常來說,合并之前先判斷兩個(gè)元素是否屬于同一集合。

void hebing(int x, int y) {

    x = find(x);

    y = find(y);

    if (x != y) { // 不在同一個(gè)集合

        father[y] = x;//將根節(jié)點(diǎn)合并

    }

}

上面三個(gè)操作是并查集常用的操作

前面的并查集的復(fù)雜度實(shí)際上在有些極端情況會(huì)很慢。比如樹的結(jié)構(gòu)正好是一條鏈，那么最壞情況下，每次查詢的復(fù)雜度達(dá)到了O(n) 。這并不是我們期望的結(jié)果。路徑壓縮的思想是，我們只關(guān)心每個(gè)結(jié)點(diǎn)的父結(jié)點(diǎn)，而并不太關(guān)心樹的真正的結(jié)構(gòu)（遞歸查找相當(dāng)浪費(fèi)時(shí)間）如下：

當(dāng)想去訪問6的根節(jié)點(diǎn)時(shí)，要訪問5的根節(jié)點(diǎn)，想去訪問5的根節(jié)點(diǎn)，又要去訪問4的根節(jié)點(diǎn)..........以此類推，此時(shí)并查集退化為線性。

這樣我們?cè)谝淮尾樵兊臅r(shí)候，可以把查詢路徑上的所有結(jié)點(diǎn)的father[i]都賦值成為根結(jié)點(diǎn)。只需要在我們之前的查詢函數(shù)上面進(jìn)行很小的改動(dòng)

int findf(int k)
{     if(f[k] == k) 
        return k;     
        return f[k] = findf(f[k]); //后來更新的點(diǎn)的根節(jié)點(diǎn)直接為最開始的點(diǎn)，一步找到總根節(jié)點(diǎn)。
}

到此，關(guān)于“C++并查集怎么實(shí)現(xiàn)”的學(xué)習(xí)就結(jié)束了，希望能夠解決大家的疑惑。理論與實(shí)踐的搭配能更好的幫助大家學(xué)習(xí)，快去試試吧！若想繼續(xù)學(xué)習(xí)更多相關(guān)知識(shí)，請(qǐng)繼續(xù)關(guān)注創(chuàng)新互聯(lián)網(wǎng)站，小編會(huì)繼續(xù)努力為大家?guī)砀鄬?shí)用的文章！

標(biāo)題名稱：C++并查集怎么實(shí)現(xiàn)-創(chuàng)新互聯(lián)
網(wǎng)頁(yè)URL：http://bm7419.com/article24/dgoeje.html

成都網(wǎng)站建設(shè)公司_創(chuàng)新互聯(lián)，為您提供App開發(fā)、企業(yè)網(wǎng)站制作、電子商務(wù)、品牌網(wǎng)站建設(shè)、定制網(wǎng)站、網(wǎng)站建設(shè)

廣告

聲明：本網(wǎng)站發(fā)布的內(nèi)容（圖片、視頻和文字）以用戶投稿、用戶轉(zhuǎn)載內(nèi)容為主，如果涉及侵權(quán)請(qǐng)盡快告知，我們將會(huì)在第一時(shí)間刪除。文章觀點(diǎn)不代表本網(wǎng)站立場(chǎng)，如需處理請(qǐng)聯(lián)系客服。電話：028-86922220；郵箱：631063699@qq.com。內(nèi)容未經(jīng)允許不得轉(zhuǎn)載，或轉(zhuǎn)載時(shí)需注明來源： 創(chuàng)新互聯(lián)