并查集(Disjiont-set)

[TOC]

更新

• 5/23/2018 更新路徑壓縮代碼

簡介

wiki上關(guān)于并查集的簡介

在計算機科學中，并查集是一種樹型的數(shù)據(jù)結(jié)構(gòu)，用于處理一些不交集（Disjoint Sets）的合并及查詢問題。有一個聯(lián)合-查找算法（union-find algorithm）定義了兩個用于此數(shù)據(jù)結(jié)構(gòu)的操作：

• Find：確定元素屬于哪一個子集。它可以被用來確定兩個元素是否屬于同一子集。
• Union：將兩個子集合并成同一個集合。

并查集主要用于解決動態(tài)連通性問題(我也不懂是什么問題).

我們用一個代表來標識一個不交集. 通常我們不關(guān)心哪個成員作為代表, 但是對于屬于同一個集合的兩個變量, 查詢應(yīng)該得到相同的代表.

舉個栗子. 假如有一個大型的計算機網(wǎng)絡(luò), 其中有很多臺計算機, 如果計算機a與計算機b連通, b與c連通, 那么a與c連通. 對于網(wǎng)絡(luò)中的兩臺計算機p, q我們可能有這些操作: 判斷p, q是否連通find(p) == find(q); 在p, q之間建立一條路線使兩者連通union(p, q).

通過上面的例子不難看出連通是一種等價關(guān)系, 它有以下性質(zhì):

• 自反性: p與p是連通的
• 對稱性: p與q連通, 則q與p連通
• 傳遞性: p與q連通且q與r連通, 則p與r連通

算法實現(xiàn)

首先我們用一個數(shù)組記錄所有元素, 對于set[i] == k , i表示一個元素, k表示元素所屬的集合, 通?？梢灾赶蚧蛘唛g接指向集合的代表來表示屬于這個集合. 當set[i] == i是表明i是一個根節(jié)點.

set[i] ==k可以理解為i, k之間有一條連通的路線, 被稱為鏈接.

初始化

讓所有元素指向自己, 表示屬于不同的集合, 此時集合中每個元素都是一個根節(jié)點

const int SIZE = 100001;
int set[SIZE];

void init(int n) {
    for (int i = 1; i <= n; ++i)
        set[i] = i;
}

Find

從x向上查找, 直到找到元素的根節(jié)點set[i] == i, 此根節(jié)點就表示這個集合

//循環(huán)寫法
int findSet(int x) {
    while (set[x] != x)
        x = set[x]
    return x;
}
//遞歸寫法
int findSet(int x) {
    if (x != set[x])
        find(set[x]);
    else
        return x;
}

Union

把兩個不同的點連起來, 對于x ,y兩個點來說, 相當與把x, y所在集合合并(傳遞性), 即x, y所在集合所以元素都連通. 所以我們可以找到兩個集合的代表(根節(jié)點), 然后把代表合并即可.

void union_set(int x, int y){
    //分別找到x, y所在集合的代表
    int rootX = find(x);
    int rootY = find(y);
    //如果已經(jīng)在一個集合中 直接return 不進行合并操作
    if (rootX == rootY) return;//這句此處看起來無關(guān)痛癢, 但是在后面的算法優(yōu)化中很重要
    set[rootX] = rootY;//選取rootY為新集合的代表, 把x所在集合合并到y(tǒng)所在集合
}

我們在選取誰合并到誰時是隨便選取的, 實際上合理的選取能夠很好地優(yōu)化算法.

圖示

findSet(6)即為set[set[set[set[6]]]] ==1, findSet(7)即為set[set[7]] == 9

unionSet(6, 7)

則rootX = 1, rootY = 9, 即set[1] = 9

unionSet(6, 7)

算法優(yōu)化

加權(quán)

上面提到合并是隨意選取的, 那么怎么選取可以優(yōu)化算法呢. 考慮find算法的過程, 從低向上查找代表, 那么樹的高度就決定了find的快慢. 所以我們合并時可以考慮把比較矮的樹合并到比較高的樹上, 這樣可以有效降低樹的高度, 從而達到優(yōu)化算法的目的.

這是一種加權(quán)并查集, 即每個代表會記錄該集合的大小(元素多少)作為代表的權(quán). 合并時我們把權(quán)小的代表所在集合(小樹)合并到權(quán)大的代表所在集合(大樹).

啟發(fā)式合并可以保證對數(shù)級別的性能O(logN).

int size[SIZE];//記錄對應(yīng)集合的元素個數(shù) 開始時需要初始化為0

void unionSet(int x, int y) {
    int rootX = findSet(x);
    int rootY = findSet(y);
    //這個return特別重要, 如果忽略, 會出現(xiàn)同一個樹的大小加倍的錯誤
    if (rootX == rootY)
        return;
    //比較兩個樹的大小 小樹合并到大樹上
    if (size[rootY] > size[rootX]) {
        set[rootX] = rootY;
        size[rootY] += size[rootX];
    } else {
        set[rootY] = rootX;
        size[rootX] += size[rootY];
    }
}

加權(quán)還有很多其他的用途, 比如統(tǒng)計一個集合的元素個數(shù), 對集合元素分類.

啟發(fā)式合并

和加權(quán)的思路一樣, 只是記錄的是樹的高度, 更加直接

int rank[SIZE];//記錄樹的高度

void unionSet(int x, int y) {
    int rootX = findSet(x);
    int rootY = findSet(y);
    if (rank[rootX] > rank[rootY]) {
        set[rootY] = rootX;
    } else {
        set[rootX] = rootY;
        if (rank[rootY] == rank[rootX])
            rank[rootY]++;
    }
}

加權(quán)與啟發(fā)式合并圖示

unionSet(6, 7), 因為6所在樹比7所在樹高且大, 所以此時set[9] = 1.

可以看到相比沒有優(yōu)化的算法, 這種合并方式有效地降低了樹高.

啟發(fā)式, 加權(quán)合并

路徑壓縮

既然把樹高降低能優(yōu)化算法, 那么我們能在find中降低樹高嗎.

我們可以在find中把查找路徑上遇到的所有節(jié)點都直接鏈接到根節(jié)點, 從而實現(xiàn)路徑壓縮, 把樹高降低.

代碼十分簡單, 甚至不比上面的復雜. 時間復雜度非常接近但是沒有達到1

int findSet(int x) {
    if (set[x] != x)
        return set[x] = findSet(set[x]);//這里最終返回都是根節(jié)點
    return x;//一定是根節(jié)點返回這句
    //然后根據(jù)根節(jié)點的返回, 更新查找路徑上其他節(jié)點
}

//一種很簡潔的寫法
int findSet(int x) {
    return (set[x] == x) ? x : (set[x] = findSet(set[x]));
}

路徑壓縮圖示

unionSet(6, 7)(沒有優(yōu)化的合并)

先會調(diào)用findSet(6), findSet(7), 查找路徑上的所以元素都會直接和根節(jié)點鏈接

findSet(6), findSet(7)

之后set[1] = 9

nuion

小結(jié)

• 路徑壓縮加上啟發(fā)式合并就是并查集算法的最優(yōu)解.
• 一般來說用路徑壓縮算法就足夠了, 可以不再用啟發(fā)式合并或者加權(quán).(減少代碼量)