Struktur data Himpunan Lepas (UFDS) digunakan untuk memodelkan sebuah kumpulan dari himpunan-himpunan yang saling lepas, dan dapat, secara efisien (hampir waktu konstan), menentukan di himpunan mana sebuah item berada, mengecek apakah dua item-item berasal dari himpunan yang sama, dan menggabungkan dua himpunan berbeda menjadi satu jika diperlukan. Himpunan Lepas dapat digunakan untuk menemukan komponen yang terhubung dalam sebuah graf tak berarah, sehingga dapat digunakan sebagai bagian dari algoritma Kruskal untuk masalah Pohon Perentangan Minimum (MST).
Catat bahwa struktur data ini mempunyai nama lain: Disjoint Sets Union (DSU).
Lihatlah visualisasi dari contoh UFDS (Himpunan Lepas) di sini!
Setiap pohon melambangkan sebuah himpunan lepas (maka sebuah kumpulan dari himpunan-himpunan lepas tersebut membentuk sebuah hutan) dan akar (root) dari setiap pohon adalah item representatif dari himpunan lepas ini.
Sekarang berhenti dan lihatlah pohon-pohon yang sekarang sedang divisualisasikan. Ada berapa jumlah item-item disana? Berapa jumlah himpunan lepas di sana? Siapa saja anggota dari setiap himpunan lepas tersebut? Apakah item representasi dari setiap himpunan lepas yang ada?
Kita bisa dengan mudah mengingat hutan pohon dengan sebuah larik p dengan ukuran N anggota-anggota di mana p[i] menyimpan orang tua dari item i dan jika p[i] = i, maka i adalah akar dari pohon ini dan juga adalah item representatif dari himpunan yang mengandung item i.
Sekali lagi, lihatlah visualisasi diatas dan tentukan nilai-nilai didalam larik p ini.
Diskusi: Jika i adalah akar dari pohon yang mempunyainya, apakah kita dapat menyimpan p[i] = -1 daripada p[i] = i? Apa implikasinya?
Pada contoh tetap yang sama, jawaban-jawaban anda harusnya p = [1, 3, 3, 3, 3, 5, 6, 5, 5, 6, 4, 8,12] dengan ukuran N = 13 untuk p[0] sampai p[12].
Anda dapat mengecek bahwa p[3] = 3, p[5] = 5, p[6] = 6, dan p[12] = 12, yang adalah konsisten dengan fakta bahwa {3,5,6,12} adalah item-item representatif (dari himpunan lepas mereka sendiri).
Kita juga menyimpan satu lagi informasi di dalam larik rank juga dengan ukuran N. Nilai dari rank[i] adalah batas-atas dari tinggi sub-pohon yang berakar pada simpul i yang akan digunakan sebagai heuristik pembimbing untuk operasi UnionSet(i, j). Anda akan menyadari nanti bahwa setelah heuristik 'kompresi-jalur' (akan dijelaskan segera) mengkompres sebuah jalur, nilai-nilai peringkat tidak lagi merefleksikan tinggi sesungguhnya dari sub-pohon tersebut.
Karena banyak item-item dengan peringkat 0, kami mengatur visualisasi sebagai berikut untuk mengurangi kekacauan: Hanya jika peringkat dari sebuah simpul i lebih besar dari 0, maka VisuAlgo akan menunjukkan nilai dari rank[i] (disingkat sebagai satu karakter r) sebagai teks berwarna merah dibawah simpul i.
Pada contoh tetap yang sama, verifikasi bahwa {1,4,6,8} memiliki peringkat 1 dan {3,5} memiliki peringkat 2, dan yang lainnya memiliki peringkat 0 (tidak ditunjukkan).
Pada saat ini, semua nilai-nilai peringkat adalah benar, yaitu mereka benar-benar mendeskripsikan tinggi dari sub-pohon yang berakar pada simpul tersebut. Kita akan segera melihat bahwa mereka tidak akan selalu benar di beberapa slide-slide berikutnya.
Terdapat lima operasi-operasi UFDS (Himpunan Lepas) dalam halaman visualisasi ini:
Contoh-Contoh, Inisialisasi(N), FindSet(i), IsSameSet(i, j), dan UnionSet(i, j).
Operasi pertama (Contoh-Contoh) adalah sederhana: Berikan daftar struktur-struktur Himpunan Lepas dengan berbagai karakteristik-karakteristik untuk titik permulaan anda. Mode kuliah maya ini selalu menggunakan contoh 'Empat Himpunan Lepas' sebagai titik permulaan.
Juga sadari bahwa tidak ada satupun dari contoh-contoh yang memiliki 'pohon yang tinggi'. Anda akan segera mengerti alasannya setelah kami menjelaskan dua heuristik-heuristik yang dipakai.
Inisialisasi(N, M): Membuat N item dan membentuk M himpunan lepas dari N item tersebut. Kita ambil dua himpunan lepas secara acak dan menggabungkan mereka sampai kita mendapatkan M himpunan lepas acak. Karena terdapat heuristik penggabungan-berdasarkan-peringkat, sangat tidak memungkinkan untuk mendapatkan sebuah pohon yang tinggi. Defaultnya adalah Inisialisasi(N, N), yakni, semuanya dengan p[i] = i dan rank[i] = 0 (pada awalnya, nilai-nilai rank ini tidak ditunjukkan).
Kompleksitas waktu dari operasi ini jelas sekali adalah O(N).
Dikarenakan terbatasnya ukuran layar, kami mengatur 1 ≤ N ≤ 32. Jelas M ≤ N.
FindSet(i): Dari simpul i, pergi ke arah atas di dalam pohon secara rekursif. Yaitu, dari simpul i, kita pergi ke simpul p[i]) hingga kita sampai pada akar dari pohon tersebut, yang adalah item representasi dengan p[i] = i dari himpunan lepas ini.
Dalam operasi FindSet(i), kami menggunakan heuristik kompresi-jalur setelah setiap panggilan kepada FindSet(i) karena sekarang setiap simpul yang terdapat dalam jalur dari simpul i ke akar dari pohon ini mengetahui bahwa akar tersebut adalah item representatif mereka dan dapat langsung menunjuk kepada akar tersebut secara langsung dalam O(1).
Jika kita melakukan FindSet(12), kita akan dengan segera mendapat simpul 12.
Jika kita melakukan FindSet(9), kita akan mendapat simpul 6 setelah 1 langkah dan tidak ada perubahan apapun.
Sekarang coba eksekusi . Jika ini adalah panggilan pertama anda pada contoh default Himpunan Lepas ini, maka fungsi tersebut akan mengembalikan simpul 3 setelah 2 langkah dan lalu mengubah struktur Himpuna Lepas karena aksi dari kompresi-jalur (yaitu, simpul 0 langsung menunjuk kepada simpul 3 secara langsung). Sadari bahwa nilai peringkat dari rank[1] = 1 sekarang menjadi salah karena simpul 1 menjadi sebuah daun baru. Tetapi, kita tidak akan mempedulikan untuk memutakhirkan nilai peringkat ini.
Sadari bahwa kali berikutnya anda mengeksekusi lagi, fungsi tersebut akan menjadi jauh lebih cepat karena jalurnya telah terkompres. Untuk saat ini, kita asumsikan bahwa FindSet(i) berjalan dalam O(1).
IsSameSet(i, j): Cek saja apakah FindSet(i) == FindSet(j). Fungsi ini digunakan secara ektensif pada algoritma MST Kruskal. Karena fungsi ini hanya memanggil operasi FindSet dua kali, kita akan mengasumsikan bahwa fungsi ini juga berjalan dalam O(1).
Perlu diingat bahwa fungsi FindSet dipanggil di dalam fungsi isSameSet, maka heuristik kompresi-jalur juga digunakan secara tidak langsung.
Jika kita memanggil IsSameSet(3, 5), kita harusnya mendapatkan false karena simpul 3 dan simpul 5 adalah item-item representatif dari himpunan-himpunan lepas mereka dan mereka berbeda.
Sekarang cobalah padah contoh default yang sama untuk melihat kompresi-jalur secara tidak langsung pada simpul 0 dan simpul 11. Kita harusnya mendapatkan false karena dua item-item representatif: simpul 3 dan simpul 5, adalah berbeda. Sadari bahwa nilai-nilai peringkat pada simpul {1, 5, 8} sekarang semuanya salah. Tetapi kita tidak akan memperbaikinya.
UnionSet(i, j): Bila i dan j berasal dari dua himpunan lepas yang berbeda pada awalnya, kita menghubungkan item representatif dari pohon/himpunan lepas yang lebih pendek dengan item representatif dari pohon/himpunan lepas yang lebih tinggi (kalau tidak, kita tidak berbuat apa-apa). Ini juga dilakukan dalam O(1).
Ini adalah efek dari heuristik penggabungan-berdasarkan-peringkat (union-by-rank) dan akan mengakibatkan pohon yang dihasilkan secara relatif pendek. Hanya jika kedua pohon-pohon memiliki tinggi yang sama sebelum digabungkan (dengan membandingkan nilai-nilai peringkat mereka secara heuristik — catat bahwa kita tidak membandingkan tinggi-tinggi mereka yang sebenarnya), maka peringkat dari pohon yang dihasilkan akan meningkat sebanyak satu unit.
Pada contoh default yang sama, cobalah . Karena pohon yang merepresentasikan himpunan lepas {6, 9} saat ini lebih tinggi (menurut nilai dari rank[6] = 1), maka pohon yang lebih pendek yang merepresentasikan himpunan lepas {12} akan ditaruh dibawah simpul 6, tanpa meningkatkan tinggi dari pohon gabungan sama sekali.
Pada contoh default yang sama, cobalah . Sadari bahwa peringkat-peringkat dari simpul 3 dan simpul 5 adalah sama, yaitu rank[3] = rank[5] = 2. Oleh karena itu, kita bisa menaruh simpul 3 dibawah simpul 5 (implementasi kami) atau simpul 5 dibawah simpul 3 (kedua opsi akan meningkatkan tinggi dari pohon gabungan sebesar 1). Sadari heuristik kompresi-jalur dipkai secara tidak langsung.
Quiz: Starting with N=8 disjoint sets, how tall (heuristically) can the resulting final tree if we call 7 UnionSet(i, j) operations strategically?
Quiz: Starting with N=8 disjoint sets, how short (heuristically) can the resulting final tree if we call 7 UnionSet(i, j) operations strategically?
Diskusi: Kenapa?
Sejauh ini, kami bilang bahwa FindSet(i), IsSameSet(i, j), dan UnionSet(i, j) berjalan dengan kompleksitas O(1). Sebenarnya, mereka berjalan dalam O(α(N)) jika Himpunan Lepas diimplementasikan dengan kedua heuristik-heuristik kompresi-jalur dan penggabungan-berdasarkan-peringkat.
Fungsi α(N) ini disebut fungsi inverse Ackermann yang berkembang dengan pelan sekali. Untuk penggunaan praktis dari struktur data Himpuan Lepas ini (asumsikan N ≤ 1M), kita punya α(1M) ≈ 1.
Untuk beberapa pertanyaan-pertanyaan menarik mengenai struktur data ini, silahkan latihan pada modul latihan Union-Find Disjoint Sets.
Setelah menyelesaikan Kuis Online dari modul Himpunan Lepas, apakah anda merasa anda telah sepenuhnya menguasai struktur data ini?
Perkenankan kami untuk menantang anda menyelesaikan dua soal pemograman yang membutuhkan struktur data Himpunan Lepas: UVa 01329 - Corporative Network dan Kattis - control.
Harap diperhatikan bahwa kedua soal tersebut adalah soal-soal International Collegiate Programming Contest (ICPC), soal-soal ini "tidak trivial".