Union-find

Union-find, yang juga dikenal sebagai struktur himpunan saling lepas (disjoint-set), menjawab pertanyaan yang BFS dan DFS jawab dengan mahal, yaitu apakah dua simpul terhubung ketika tepi terus ditambahkan di tengah jalan. Topik ini membangun strukturnya dari nol dengan dua peningkat klasik, yaitu path compression dan union by rank, lalu menghitung komponen yang berkurang setiap kali satu tepi masuk. Versi Java dengan logika yang sama menyusul, dan jejak pohonnya digambar pada diagram.

Masalah komponen dinamis#

Komponen terhubung mudah dihitung saat grafnya statis, cukup satu DFS dari setiap simpul yang belum dikunjungi. Persoalan muncul ketika tepi ditambahkan sambil jalan, misalnya menyambung jaringan antarkota satu per satu sambil terus ditanya apakah dua kota sudah tersambung. Menjalankan penelusuran penuh untuk setiap pertanyaan berbiaya $O(V + E)$, dan totalnya membengkak ketika pertanyaannya ribuan. Union-find menjawab tiap pertanyaan dalam waktu yang hampir konstan setelah strukturnya berdiri.

Struktur ini menyimpan n himpunan yang mula-mula masing-masing berisi satu simpul, lalu operasi union menggabungkan dua himpunan menjadi satu. Operasi find mengembalikan perwakilan himpunan, sering disebut akar, yang nilainya sama untuk seluruh anggota satu himpunan. Dua simpul terhubung persis ketika find keduanya mengembalikan akar yang sama.

Hutan induk dengan find dan union by rank#

Representasinya seminimal mungkin, yaitu satu array induk yang panjangnya n dan awalnya berisi 0 sampai n - 1, karena setiap simpul menjadi induk dirinya sendiri. Akar sebuah himpunan adalah simpul yang induknya dirinya sendiri, dan rantai induk di bawahnya membentuk pohon. Menggabungkan dua himpunan berarti menempelkan akar pohon yang satu di bawah akar pohon lainnya, dan tanpa aturan tambahan pohon ini bisa memanjang seperti rantai. Union by rank mencegahnya dengan mencatat perkiraan tinggi pohon pada array peringkat, lalu selalu menempelkan pohon yang lebih pendek di bawah yang lebih tinggi.

Peringkat hanya bertambah bila kedua pohon yang digabung sama tingginya, dan pemenangnya naik satu tingkat. Tinggi pohon karenanya hanya bisa berlipat ganda, sehingga dibatasi $O(\log n)$. Gabungan dengan path compression menurunkan biaya tiap operasi menjadi hampir konstan. Pada analisis amortisasi, biaya itu dinyatakan $O(\alpha(n))$ dengan $\alpha$ sebagai invers fungsi Ackermann yang nilainya praktis tak pernah melebihi 4 untuk ukuran masukan nyata. Angka ini disebut tanpa pembuktian, karena analisisnya berada jauh di luar kebutuhan implementasi.

Path compression#

Path compression memperpendek rantai induk setiap kali find berjalan. Caranya, setiap simpul yang dilintasi ditautkan langsung ke kakeknya, sehingga rantai yang panjang menyusut drastis dalam satu panggilan. Biaya tambahannya nyaris nol dalam arti amortisasi, karena pekerjaan memperpendek ini langsung dibayar oleh find berikutnya yang lebih cepat.

Diagram berikut memperlihatkan efeknya pada rantai 3 menuju 2 menuju 0. Sebelum find(3), simpul 3 harus melewati 2 untuk mencapai akar 0. Sesudahnya, 3 menempel langsung di 0, dan panggilan find apa pun berikutnya selesai dalam satu langkah.

Implementasi dari nol#

Berkas berikut menyatukan semuanya. Find ditulis sebagai perulangan yang sekaligus memampatkan jalur yang dilaluinya, sedangkan union mengembalikan False bila kedua simpul ternyata sudah satu himpunan. Nilai kembalian itu dipakai untuk menghitung komponen, karena setiap union yang benar-benar menggabungkan mengurangi jumlah komponen tepat satu. Lima tepi ditambahkan satu per satu dan jumlah komponennya dicetak setiap kali.

# Union-find dari nol: find dengan path compression dan union by rank.
induk = list(range(6))  # induk[simpul], awalnya menunjuk diri sendiri
peringkat = [0] * 6     # perkiraan tinggi pohon himpunan

def find(x):
    while induk[x] != x:
        induk[x] = induk[induk[x]]  # path compression: lompat ke kakek
        x = induk[x]
    return x

def union(a, b):
    akar_a, akar_b = find(a), find(b)
    if akar_a == akar_b:
        return False  # kedua simpul memang sudah satu himpunan
    if peringkat[akar_a] < peringkat[akar_b]:
        akar_a, akar_b = akar_b, akar_a
    induk[akar_b] = akar_a  # pohon yang lebih pendek menempel di akar lain
    if peringkat[akar_a] == peringkat[akar_b]:
        peringkat[akar_a] += 1
    return True

def jumlah_komponen():
    return sum(1 for x in range(6) if find(x) == x)

tepi = [(0, 1), (2, 3), (1, 2), (4, 5), (3, 4)]
print("Komponen awal:", jumlah_komponen())
for u, v in tepi:
    union(u, v)
    print(f"Setelah tepi ({u}, {v}):", jumlah_komponen(), "komponen")
print("Induk akhir  :", induk)

Komponen awal: 6
Setelah tepi (0, 1): 5 komponen
Setelah tepi (2, 3): 4 komponen
Setelah tepi (1, 2): 3 komponen
Setelah tepi (4, 5): 2 komponen
Setelah tepi (3, 4): 1 komponen
Induk akhir  : [0, 0, 0, 0, 0, 0]

Komponen menurun dari enam ke satu seiring lima tepi menggabungkan himpunannya satu demi satu. Bila ada tepi yang menghubungkan dua simpul yang sudah satu himpunan, union mengembalikan False dan jumlah komponen tidak berubah sama sekali, perilaku yang nanti dipakai untuk menemukan tepi berlebih. Baris terakhir menunjukkan seluruh simpul menunjuk akar 0, hasil kerja path compression dan union by rank yang meratakan pohonnya.

Padanan Java#

Versi Java memakai array statis dengan logika yang sama persis, mulai dari find yang melompat ke kakek sampai union by rank dengan pertukaran nilai sementara. Arrays.toString mencetak isi array induk agar bentuknya mirip keluaran Python. Struktur seperti ini biasanya dibungkus kelas sendiri pada kode produksi, tetapi versi polos ini lebih mudah dibaca sebagai demo.

// Union-find dengan path compression dan union by rank.
public class UnionFind {
    static int[] induk = {0, 1, 2, 3, 4, 5};
    static int[] peringkat = new int[6];

    static int find(int x) {
        while (induk[x] != x) {
            induk[x] = induk[induk[x]]; // path compression: lompat ke kakek
            x = induk[x];
        }
        return x;
    }

    static void union(int a, int b) {
        int akarA = find(a);
        int akarB = find(b);
        if (akarA == akarB) {
            return; // kedua simpul memang sudah satu himpunan
        }
        if (peringkat[akarA] < peringkat[akarB]) {
            int sementara = akarA;
            akarA = akarB;
            akarB = sementara;
        }
        induk[akarB] = akarA; // pohon yang lebih pendek menempel di akar lain
        if (peringkat[akarA] == peringkat[akarB]) {
            peringkat[akarA]++;
        }
    }

    static int jumlahKomponen() {
        int jumlah = 0;
        for (int x = 0; x < 6; x++) {
            if (find(x) == x) {
                jumlah++;
            }
        }
        return jumlah;
    }

    public static void main(String[] args) {
        int[][] tepi = {{0, 1}, {2, 3}, {1, 2}, {4, 5}, {3, 4}};
        System.out.println("Komponen awal: " + jumlahKomponen());
        for (int[] e : tepi) {
            union(e[0], e[1]);
            System.out.println("Setelah tepi (" + e[0] + ", " + e[1] + "): "
                + jumlahKomponen() + " komponen");
        }
        System.out.println("Induk akhir  : " + java.util.Arrays.toString(induk));
    }
}

Komponen awal: 6
Setelah tepi (0, 1): 5 komponen
Setelah tepi (2, 3): 4 komponen
Setelah tepi (1, 2): 3 komponen
Setelah tepi (4, 5): 2 komponen
Setelah tepi (3, 4): 1 komponen
Induk akhir  : [0, 0, 0, 0, 0, 0]

Keluarannya identik baris demi baris dengan versi Python, termasuk isi array induk akhir yang seluruhnya 0. Kesamaan ini menjadi alat uji yang murah, karena setiap selisih antar bahasa langsung menunjuk baris yang salah. Kompleksitas keseluruhan demo mendekati $O(E)$ untuk E tepi, karena tiap operasi tepinya berbiaya hampir konstan.

Kesalahan umum#

Sumber kesalahan kedua adalah mengurangi penghitung komponen tanpa membaca kembalian union. Penghitung bisa turun padahal tidak ada gabungan yang terjadi, persis pada tepi yang menghubungkan dua simpul satu himpunan. Selipkan pemeriksaan kembalian union sebelum mengurangi penghitung, atau jadikan kembalian itu satu-satunya sinyal.

Jebakan ketiga berupa union yang selalu menempel akar pertama tanpa memandang peringkat. Kode itu sah secara logika, tetapi pada masukan yang sengaja berbentuk rantai, pohonnya memanjang seperti linked list dan find merosot ke $O(n)$. Union by rank ada untuk mencegah kasus ini, dan biayanya hanya satu array tambahan.

Ringkasan#

• Union-find menyimpan himpunan saling lepas sebagai hutan pohon induk, dengan find sebagai pencari akar dan union sebagai penggabungnya.
• Path compression melompat ke kakek saat find, sedangkan union by rank menempelkan pohon yang lebih pendek di bawah yang lebih tinggi.
• Gabungan keduanya membuat tiap operasi hampir konstan, dinyatakan $O(\alpha(n))$ pada analisis amortisasi.
• Kembalian union berupa sinyal penggabungan, dan nilainya dipakai untuk menghitung komponen yang berkurang saat tepi ditambahkan.

Referensi#

• Disjoint-set data structure — Wikipedia — Path compression, union by rank, dan kompleksitas amortisasinya.
• Algorithms, 4th Edition — Princeton University — Bab union-find berisi implementasi referensi dan analisisnya.