C++並查集常用操作

並查集是一種樹型的數據結構,用於處理一些不相加集合的合並和查詢問題。在使用中常常以森林來表示。並查集也是用來維護集合的,和前面學習的set不同之處在於,並查集能很方便地同時維護很多集合。如果用set來維護會非常的麻煩。並查集的核心思想是記錄每個結點的父親結點是哪個結點。

前言

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

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

初始化：每個結點單獨作為一個集合

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

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

合並之前，應先判斷兩個元素是否屬於同一集合，用上面的“查詢”來實現

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

void init() {

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

        father[i] = i;

    }

}

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

int get(int x) {

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

        return x; 

    }

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

}

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

void hebing(int x, int y) {

    x = find(x);

    y = find(y);

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

        father[y] = x;//將根節點合並

    }

}

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

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

當想去訪問6的根節點時，要訪問5的根節點，想去訪問5的根節點，又要去訪問4的根節點……….以此類推，此時並查集退化為線性。

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

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

初步學習理解，如有不足請指出，謝謝

到此這篇關於C++並查集基礎的文章就介紹到這瞭,更多相關C++並查集內容請搜索WalkonNet以前的文章或繼續瀏覽下面的相關文章希望大傢以後多多支持WalkonNet！