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

這篇文章主要介紹了C++的并查集如何實現(xiàn)的相關(guān)知識，內(nèi)容詳細(xì)易懂，操作簡單快捷，具有一定借鑒價值，相信大家閱讀完這篇C++的并查集如何實現(xiàn)文章都會有所收獲，下面我們一起來看看吧。

前言

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

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

常用操作

初始化：每個結(jié)點單獨作為一個集合

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

合并：將兩個元素所在的集合，合并為一個集合

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

算法實現(xiàn)

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

void init() {

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

        father[i] = i;

    }

}

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

int get(int x) {

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

        return x; 

    }

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

}

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

void hebing(int x, int y) {

    x = find(x);

    y = find(y);

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

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

    }

}

上面三個操作是并查集常用的操作

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

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

這樣我們在一次查詢的時候，可以把查詢路徑上的所有結(jié)點的father[i]都賦值成為根結(jié)點。只需要在我們之前的查詢函數(shù)上面進(jìn)行很小的改動

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

關(guān)于“C++的并查集如何實現(xiàn)”這篇文章的內(nèi)容就介紹到這里，感謝各位的閱讀！相信大家對“C++的并查集如何實現(xiàn)”知識都有一定的了解，大家如果還想學(xué)習(xí)更多知識，歡迎關(guān)注億速云行業(yè)資訊頻道。