The Union-Find Disjoint Sets (UFDS) data structure is used to model a collection of disjoint sets, which is able to efficiently (i.e., in nearly constant time) determine which set an item belongs to, test if two items belong to the same set, and union two disjoint sets into one when needed. It can be used to find Connected Components (CCs) in an undirected graph, and can hence be used as part of Kruskal's algorithm for the Minimum Spanning Tree (MST) problem.
Note that this data structure has another alternative name: 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?
As we fixed the default example for this e-Lecture, your answers should be: N = 13 and there are 4 disjoint sets: {0, 1, 2, 3, 4, 10}, {5, 7, 8, 11}, {6, 9}, {12} with the underlined members be the representative items (of their own disjoint set).
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?
On the same fixed example, your answers should be p = [1, 3, 3, 3, 3, 5, 6, 5, 5, 6, 4, 8, 12] of size N = 13 ranging from p[0] to p[12].
You can check that p[3] = 3, p[5] = 5, p[6] = 6, and p[12] = 12, which are consistent with the fact that {3, 5, 6, 12} are the representative items (of their own disjoint set).
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.
On the same fixed example, verify that {1, 4, 6, 8} have rank 1 and {3, 5} have rank 2, with the rest having rank 0 (not shown).
At this point of time, all rank values are correct, i.e., they really describe the height of the subtree rooted at that vertex. We will soon see that they will not be always correct in the next few slides.
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).
If we execute FindSet(12), we will immediately get vertex 12.
If we execute FindSet(9) we will get vertex 6 after 1 step and no other change.
Now try executing . If this is your first call on this default UFDS example, it will return vertex 3 after 2 steps and then modify the underlying UFDS structure due to path-compression in action (that is, vertex 0 points to vertex 3 directly). Notice that rank value of rank[1] = 1 is now wrong as vertex 1 becomes a new leaf. However, we will not bother to update its value for efficiency.
Notice that the next time you execute again, it will be (much) faster as the path has been compressed. For now, we assume that FindSet(i) runs in 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.
If we call IsSameSet(3, 5), we should get false as vertex 3 and vertex 5 are representative items of their respective disjoint sets and they are different.
Now try on the same default example to see indirect path-compression on vertex 0 and vertex 11. We should get false as the two representative items: vertex 3 and vertex 5, are different. Notice that the rank values at vertex {1, 5, 8} are now wrong. But we will not fix them, again — for efficiency.
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.
Even after clearing the Online Quiz of this UFDS module, do you think that you have really mastered this data structure?
Let us challenge you by asking you to solve three programming problems that somewhat requires the usage of this Union-Find Disjoint Sets data structure: LeetCode - number-of-provinces, UVa 01329 - Corporative Network, and Kattis - control.
Beware that two of the three problems are actual International Collegiate Programming Contest (ICPC) problems, i.e., they are "not trivial".