Disjoint-set Data Structure

主要特性

Disjoint-set（並查集）是一種數據結構，用於追蹤和管理多個不相交的集合。其核心功能是快速判斷兩個元素是否屬於同一個集合，以及快速合併兩個集合。這一特性讓它在圖論、網絡連接和其他需要動態集合管理的情境下非常實用。

具體而言，你可以將它想像為一個社交網絡，其中的人們形成了不同的社交圈子。在這裡，你可以快速地確定兩個人是否屬於同一個社交圈子，或將兩個社交圈子合併成一個。

基本操作

一個常見的 Disjoint-set 支持以下操作：

• MAKE_SET(x)：建立一個新的只包含元素 x 的集合。
• FIND_SET(x)：返回包含元素 x 的集合的代表元素。
• UNION(x, y)：將包含 x 和 y 的兩個集合合併為一個。

void make_set(int v) {
    parent[v] = v;
}

int find_set(int v) {
    if (v == parent[v])
        return v;
    return find_set(parent[v]);
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b)
        parent[b] = a;
}

Disjoint-set 的應用

由於 Disjoint-set 可以快速地進行集合判斷和合併，它在以下情境中是非常有用的：

• 最小生成樹算法：如 Kruskal's algorithm。
• 迷宮生成和解決。
• 電路模擬：確定電路中的多個節點是否連接。
• 劃分等價類：如集合劃分或字符串等價。

優化

在實作 Disjoint-set 時，一般會使用 "union by rank" 和 "path compression" 的優化技術來改善其效率。時間複雜度通常為：

• MAKE_SET：O(1)
• FIND_SET：接近 O(1)，在實際應用中經常被視為常數時間。
• UNION：也接近 O(1)

這些操作的攤銷時間複雜度可以達到近乎常數時間，這是通過 "union by rank" 和 "path compression" 實現的。

path compression：

int find_set(int v) {
    if (v == parent[v])
        return v;
    return parent[v] = find_set(parent[v]);
}

union by rank：

void make_set(int v) {
    parent[v] = v;
    size[v] = 1;
}

void union_sets(int a, int b) {
    a = find_set(a);
    b = find_set(b);
    if (a != b) {
        if (size[a] < size[b])
            swap(a, b);
        parent[b] = a;
        size[a] += size[b];
    }
}

延伸應用

Disjoint-set 資料結構與其他資料結構和算法有一定的關聯性。例如，它與圖論中的連通分量（Connected Components）有密切的關係，並且在計算幾何（Computational Geometry）中也有應用。