Disjoint Sets

Apa itu Disjoint Sets?

Disjoint sets, juga dikenal sebagai struktur data union-find, adalah struktur data yang memelihara kumpulan himpunan yang saling lepas. Struktur data ini menyediakan dua operasi utama, yaitu union dan find. Operasi union menggabungkan dua himpunan menjadi satu, dan operasi find menentukan himpunan mana suatu elemen tertentu termasuk. Disjoint sets dapat digunakan untuk merepresentasikan dan memanipulasi partisi himpunan atau grafik secara efisien, seperti pada algoritma Kruskal untuk mencari pohon rentang minimum.

Notes

• Operasi union menggabungkan dua set menjadi satu dengan mengubah pointer induk dari akar satu set untuk menunjuk ke akar set lain.
• Operasi find secara rekursif mengikuti pointer induk sampai mencapai akar set dan mengembalikan akar tersebut.
• Untuk mengoptimalkan operasi find, dapat dilakukan kompresi path dengan mengubah pointer induk dari semua elemen di dalam jalur untuk menunjuk langsung ke akar, sehingga membuat struktur menjadi datar (flattening the tree).

Ilustrasi

Berikut adalah contoh set/himpunan angka yang isinya mereka sendiri,

Kita harus melakukan union untuk menggabungkan 2 himpunan menjadi 1 himpunan.

Kita bisa lihat himpunan (1, 2) dan (5, 4). Lalu kita lakukan union lagi.

Hasilnya sebagai berikut, himpunan dengan isi (1, 2, 3) dan (4, 5).

Implementasi

#include <stdio.h>
#include <stdlib.h>

#define MAX_SIZE 100

int parent[MAX_SIZE]; // parent[i] stores the parent of i

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

int find_set(int x) {
    if (parent[x] == x) {
        return x;
    }
    return parent[x] = find_set(parent[x]); // path compression
}

void union_sets(int x, int y) {
    int root_x = find_set(x);
    int root_y = find_set(y);
    parent[root_x] = root_y;
}

void print_sets(int n) {
    printf("############\n");

    for (int i = 1; i <= n; i++) {
        int root_i = find_set(i);
        printf("parent[%d] = %d\n", i, root_i);
    }
}

int main() {
    int n = 5; // number of elements
    for (int i = 1; i <= n; i++) {
        make_set(i);
    }

    union_sets(1, 2);
    print_sets(n);

    union_sets(4, 5);
    print_sets(n);

    union_sets(2, 3);
    print_sets(n);

    return 0;
}

Output

############
parent[1] = 2
parent[2] = 2
parent[3] = 3
parent[4] = 4
parent[5] = 5
############
parent[1] = 2
parent[2] = 2
parent[3] = 3
parent[4] = 5
parent[5] = 5
############
parent[1] = 3
parent[2] = 3
parent[3] = 3
parent[4] = 5
parent[5] = 5