高階資料結構:並查集

語言: CN / TW / HK

本文已參與「新人創作禮」活動,一起開啟掘金創作之路。

並查集(Union Find)

定義

孩子節點指向父親節點的一種很不一樣的樹形結構,對於一組資料,主要支援兩個動作:

  • $union(p, q)$:把元素p和元素q所在的兩個不相交的集合合併為一個集合
  • $isConnected(p,q)$:查詢元素p和元素q是否在同一個集合中

基本的資料表示

image-20220219205109347.png

$0/1$表示不同的集合,上圖中元素$[0,2,4,6,8]$屬於同一個集合,元素$[1,3,5,7,9]$的屬於同一個集合

介面定義

java /** * 並查集支援的操作 */ public interface UF {    boolean isConnected(int p, int q);    void unionElements(int p, int q);    int getSize(); }

版本一:Quick Find

初始化

java public class UnionFind1 implements UF{    private int[] id;                                       // 節點x的父節點是id[x]    public UnionFind1(int size) {        id = new int[size]; ​        for (int i = 0; i < id.length; i++) {            id[i] = i;                                    // 此時 每個元素都所屬不同的集合       }   }        @Override    public int getSize() {        return id.length;   } }

isConnected

image-20220219211236051.png

java /**  * 查詢元素p所對應的集合編號  * O(1)  * @param p  * @return  */ private int find(int p) {    if (p < 0 || p >= id.length) {        throw new IllegalArgumentException("p is out of bound.");   }    return id[p]; } ​ /**  * 元素p和元素q是否屬於同一個集合  * O(1)  * @param p  * @param q  * @return  */ @Override public boolean isConnected(int p, int q) {    return find(p)==find(q); }

Union

image-20220219210411169.png

可以將4所屬集合中的元素都合併到1所屬集合中,也可以將1所屬集合中的元素都合併到2所屬集合中:

image-20220219210541493.png java /** * 合併元素pq所屬的集合 * O(n) * @param p * @param q */ @Override public void unionElements(int p, int q) {    int pId = find(p);    int qId = find(q); ​    if (pId == qId) {        return ;   } ​    for (int i = 0; i < id.length; i++) {        if (id[i] == pId) {            id[i] = qId;       }   } }

時間複雜度分析

Quick Find本質上屬於用陣列模擬並查集的操作

  • unionElements(p,q):時間複雜度為$O(n)$
  • isConnected(p,q):時間複雜度為$O(1)$

版本二:Quick Union

基本思想

將每一個元素,看做是一個節點,節點之間相連線形成樹形結構,該樹形結構中是孩子節點指向父親節點:

image-20220219212604453.png

上圖的資料表示如下:

image-20220219213028488.png

Quick Union下的資料表示

image-20220219212709195.png

image-20220219213152818.png

初始化時,相當於有10顆樹

java public class UnionFind2 implements UF{    private int[] parent; ​    public UnionFind2(int size) {        parent = new int[size]; ​        for (int i = 0; i < size; i++) {            parent[i] = i;                 // 初始化:每個節點指向本身,即每個節點都是一棵獨立的樹       }   } ​    @Override    public int getSize() {        return parent.length;   } }

Union

$Union(4,3)$:讓4節點指向3節點,陣列中表示即為parent[4]=3

image-20220219213302811.png

image-20220219213413847.png

$Union(3,8)$:讓3節點指向8節點,陣列中表示即為parent[3]=8

image-20220219213527738.png

image-20220219213639181.png

$Union(6,5)$:讓6節點指向5節點,陣列中表示即為parent[6]=5

image-20220220105052289.png

image-20220220105144689.png

$Union(9,4)$:讓9節點指向4節點所在樹的根節點,涉及查詢操作,查詢4所在樹的根節點,如果讓9直接指向4就形成了連結串列,體現不出樹的優勢,陣列中表示即為parent[9]=8

image-20220220105602437.png

image-20220220105640997.png

$Union(6,2)$:讓6節點所在樹的根節點指向2節點所在樹的根節點

image-20220220105911331.png

```java /* * 查詢元素p所對應的集合編號 * O(h),h為樹的高度 * @param p * @return / private int find(int p) {

if (p < 0 || p >= parent.length) {        throw new IllegalArgumentException("p is out of bound.");   }

while (p != parent[p]) {       // 尋找根節點        p = parent[p];   }    return p; } /* * 合併元素pq所屬的集合 * O(h),h為樹的高度 * @param p * @param q / @Override public void unionElements(int p, int q) {    int pRoot = find(p);    int qRoot = find(q);

if (pRoot == qRoot) {        return ;   }

parent[pRoot] = qRoot; } ```

isConnected

java /** * 元素p和元素q是否屬於同一個集合 * O(h),h為樹的高度 * @param p * @param q * @return */ @Override public boolean isConnected(int p, int q) {    return find(p) == find(q); }

時間複雜度分析

  • unionElements(p,q)isConnected(p,q)的時間複雜度均為$O(h)$,$h$為樹的高度,通常樹高遠遠小於資料總量$n$

版本三:Quick Union基於size的優化

版本二中由於在合併兩個樹時不對兩個樹的形狀做判斷,因此有可能形成連結串列,例如下圖經由$Union(0,1)$、$Union(0,2)$、$Union(0,3)$形成:

image-20220220111647149.png

一個簡單的解決方案是考慮樹的節點數目size

image-20220220111859615.png

例如上圖考慮$Union(9,4)$,如果讓8節點直接指向9,那麼新的樹高到達了4,但如果讓9節點指向8,那麼新的樹高仍然為3

image-20220220112105512.png

因此讓節點數目少的那顆樹的根節點指向節點數目多的那顆樹的根節點,這樣有更高的概率讓形成的新樹的高度比較低

```java /* * 優化第二版的unionElements方法 * 基於size的優化 / public class UnionFind3 implements UF { private int[] parent; private int[] sz;         // sz[i]表示以i為根的集合中元素個數

public UnionFind3(int size) {
    parent = new int[size];
    sz = new int[size];
    for (int i = 0; i < size; i++) {
        parent[i] = i;
        sz[i] = 1;
    }
}

@Override
public int getSize() {
    return parent.length;
}

/**
 * 查詢元素p所對應的集合編號
 * O(h),h為樹的高度
 * @param p
 * @return
 */
private int find(int p) {

​ if (p < 0 || p >= parent.length) { throw new IllegalArgumentException("p is out of bound."); }

    while (p != parent[p]) {
        p = parent[p];
    }

    return p;
}

/**
 * 元素p和元素q是否屬於同一個集合
 * O(h)
 * @param p
 * @param q
 * @return
 */
@Override
public boolean isConnected(int p, int q) {
    return find(p) == find(q);
}

/**
 * 合併元素pq所屬的集合
 * O(h)
 * @param p
 * @param q
 */
@Override
public void unionElements(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);

    if (pRoot == qRoot) {
        return ;
    }

    /*
     * 讓元素個數比較少的根節點指向元素個數比較多的根節點
     * 避免形成連結串列
     */
    if (sz[pRoot] < sz[qRoot]) {
        parent[pRoot] = qRoot;   // pRoot指向qRoot
        sz[qRoot] += sz[pRoot];
    } else {
        parent[qRoot] = pRoot;
        sz[pRoot] += sz[qRoot];
    }
}

} ```

版本四:Quick Union基於rank的優化

版本三的優化思路是在每次合併兩顆樹時,儘量保證形成的新樹的高度不會增加

image-20220220112955768.png

考慮對上圖所示的並查集進行$Union(4,2)$操作,根據版本三的執行邏輯,應該是節點8指向節點7,但是明顯樹高增加了

image-20220220113259302.png

所以更加合理的合併方案應該是讓樹高比較低的樹的根節點指向樹高比較高的根節點:

image-20220220113531341.png

因此合併時應該讓深度比較低的那顆樹向深度比較高的那顆樹合併,使用rank[i]記錄根節點為i的樹的高度

```java /* * 基於rank的優化 / public class UnionFind4 implements UF { private int[] parent; private int[] rank; // rank[i]表示以i為根的集合所表示的樹的層數

public UnionFind4(int size) {
    parent = new int[size];
    rank = new int[size];
    for (int i = 0; i < size; i++) {
        parent[i] = i;
        rank[i] = 1;
    }
}

/**
     * 查詢元素p所對應的集合編號
     * O(h),h為樹的高度
     *
     * @param p
     * @return
     */
private int find(int p) {

    if (p < 0 || p >= parent.length) {
        throw new IllegalArgumentException("p is out of bound.");
    }

    while (p != parent[p]) {
        p = parent[p];
    }
    return p;
}

@Override
public int getSize() {
    return parent.length;
}

/**
     * 元素p和元素q是否屬於同一個集合
     * O(h)
     *
     * @param p
     * @param q
     * @return
     */
@Override
public boolean isConnected(int p, int q) {
    return find(p) == find(q);
}

/**
     * 合併元素pq所屬的集合
     * O(h)
     *
     * @param p
     * @param q
     */
@Override
public void unionElements(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);

    if (pRoot == qRoot) {
        return;
    }

    /*
     * 根據兩個元素所在樹的rank不同判斷合併方向
     * 將rank低的集合合併到rank高的集合上
     */
    if (rank[pRoot] < rank[qRoot]) {
        parent[pRoot] = qRoot;   // pRoot指向qRoot
    } else if (rank[qRoot] < rank[pRoot]) {
        parent[qRoot] = pRoot;
    } else {
        parent[qRoot] = pRoot;
        rank[pRoot] += 1;       
    }
}

} ```

版本五:路徑壓縮Path Compression

image-20220220114424537.png

對於如上的三棵樹,雖然表示的是同一個集合,但是由於樹高不同,因此執行find操作的效率也不同,最理想的情況當然是最下面那種樹,樹高為2,路徑壓縮就是在並查集中將高樹壓縮為矮樹,路徑壓縮發生在執行find操作時,在查詢根節點的過程中,順便讓樹高降低:

image-20220220153847070.png

parent[p]=parent[parent[p]]表示讓p節點指向其父節點的父節點

例如查詢4節點的父節點,那麼執行完parent[p]=parent[parent[p]]後,4節點的父節點為2節點:

image-20220220154131664.png

此時2節點仍然不是根節點,繼續向上遍歷:

image-20220220154334673.png

至此就找到了4的根節點0,同時在查詢的過程中將樹的高度由5降為3,這個過程就叫做路徑壓縮。

image-20220220154537182.png

```java /* * 路徑壓縮 * 優化find方法 / public class UnionFind5 implements UF{ private int[] parent; private int[] rank; // rank[i]表示以i為根的集合所表示的樹的層數 // 不反應高度/深度

public UnionFind5(int size) {
    parent = new int[size];
    rank = new int[size];
    for (int i = 0; i < size; i++) {
        parent[i] = i;
        rank[i] = 1;
    }
}

@Override
public int getSize() {
    return parent.length;
}

/**
 * 查詢元素p所對應的集合編號
 * O(h),h為樹的高度
 * @param p
 * @return
 */
private int find(int p) {

    if (p < 0 || p >= parent.length) {
        throw new IllegalArgumentException("p is out of bound.");
    }

    while (p != parent[p]) {
        // 相對於版本四,僅增加如下一行程式碼
        parent[p] = parent[parent[p]];      // 路徑壓縮 
        p = parent[p];                      // 繼續查詢根節點
    }
    return p;
}

/**
 * 元素p和元素q是否屬於同一個集合
 * O(h)
 * @param p
 * @param q
 * @return
 */
@Override
public boolean isConnected(int p, int q) {
    return find(p) == find(q);
}

/**
 * 合併元素pq所屬的集合
 * O(h)
 * @param p
 * @param q
 */
@Override
public void unionElements(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);

    if (pRoot == qRoot) {
        return ;
    }

    /*
     * 根據兩個元素所在樹的rank不同判斷合併方向
     * 將rank低的集合合併到rank高的集合上
     * 並不實際反應節點的深度/高度值
     */
    if (rank[pRoot] < rank[qRoot]) {
        parent[pRoot] = qRoot;   // pRoot指向qRoot

    } else if (rank[qRoot] < rank[pRoot]) {
        parent[qRoot] = pRoot;
    } else {
        parent[qRoot] = pRoot;
        rank[pRoot] += 1;
    }
}

} ```

版本六:利用遞迴優化路徑壓縮

在上一版本中,利用路徑壓縮將下圖中左邊的樹壓縮成右邊的形狀,效能已經有了較大提升

image-20220220155332768.png

但是在最理想的情況下, 希望將上圖左邊的樹直接壓縮成高度為2的樹:

image-20220220155616638.png

這樣一種路徑壓縮可以利用遞迴來實現,在查詢4的根節點過程中,將4以及之前的節點全部指向根節點

```java /* * 路徑壓縮 * 利用遞迴 優化find方法 / public class UnionFind6 implements UF{ private int[] parent; private int[] rank; // rank[i]表示以i為根的集合所表示的樹的層數 // 不反應高度/深度

public UnionFind6(int size) {
    parent = new int[size];
    rank = new int[size];
    for (int i = 0; i < size; i++) {
        parent[i] = i;
        rank[i] = 1;
    }
}

@Override
public int getSize() {
    return parent.length;
}

/**
 * 查詢元素p所對應的集合編號
 * O(h),h為樹的高度
 * @param p
 * @return 根節點
 */
private int find(int p) {

    if (p < 0 || p >= parent.length) {
        throw new IllegalArgumentException("p is out of bound.");
    }

    // p 節點以及p節點之前的節點都將指向根節點
    if (p != parent[p]) {
        parent[p] = find(parent[p]);
    }
    return parent[p];
}

/**
 * 元素p和元素q是否屬於同一個集合
 * O(h)
 * @param p
 * @param q
 * @return
 */
@Override
public boolean isConnected(int p, int q) {
    return find(p) == find(q);
}

/**
 * 合併元素pq所屬的集合
 * O(h)
 * @param p
 * @param q
 */
@Override
public void unionElements(int p, int q) {
    int pRoot = find(p);
    int qRoot = find(q);

    if (pRoot == qRoot) {
        return ;
    }

    /*
     * 根據兩個元素所在樹的rank不同判斷合併方向
     * 將rank低的集合合併到rank高的集合上
     * 並不實際反應節點的深度/高度值
     */
    if (rank[pRoot] < rank[qRoot]) {
        parent[pRoot] = qRoot;   // pRoot指向qRoot

    } else if (rank[qRoot] < rank[pRoot]) {
        parent[qRoot] = pRoot;
    } else {
        parent[qRoot] = pRoot;
        rank[pRoot] += 1;
    }
}

} ```

版本六的效能不一定高於版本五,遞迴是有一定的效能開銷的

在版本五中,多執行幾次find操作也是可以將樹的高度壓縮為2的,例如再一次執行find(4)+find(3)

image-20220220161649877.png

image-20220220161715773.png

時間複雜度分析

加入路徑壓縮後並查集的時間複雜度嚴格意義上為:$\ O(log^*n)->iterated\,\,logarithm$

$$ log^n=\begin{cases} 0 & \text{ if } n \le 1 \ 1+log^(logn) & \text{ if } n > 1 \end{cases} $$ 近乎是$O(1)$級別的。

應用

  • 連線問題 Connectivity Problem

    • 網路中節點間的連線狀態
    • 數學中的集合類實現

Reference