Disjoint Set Union
Penulis: Polikarpus
Disjoint Set Union (Kumpulan himpunan yang tak beririsan) atau yang biasa disingkat DSU adalah struktur data yang mampu menampung sekumpulan himpunan. Tiap himpunan tidak beririsan satu sama lain, sehingga tidak ada elemen yang berada pada 2 himpunan berbeda. DSU memiliki 3 operasi utama, yaitu:
findberguna untuk mencari sebuah perwakilan dalam himpunansameberguna untuk memeriksa apakah dua himpunan merupakan himpunan yang samajoinberguna untuk menggabungkan 2 himpunan
Struktur
Dalam DSU, tiap himpunan direpresentasikan dalam sebuah pohon. Dalam pohon tersebut, akar dari pohon tersebut merupakan perwakilan dari sebuah himpunan. Perwakilan inilah yang menjadi identitas dari tiap himpunan. Sebagai contoh apabila kita memiliki himpunan {1, 2, 3}, {4},{5, 6, 7, 8}
Dalam hal ini, himpunan pertama diwakilkan oleh 2, himpunan kedua diwakilkan oleh 4, dan himpunan ketiga diwakilkan oleh 5. Terlihat bahwa untuk tiap elemen (kecuali akar) dalam himpunan akan menunjuk kepada suatu elemen lain. Apabila kita melakukan penjelajahan graf dari suatu elemen kita akan berakhir pada akar. Sebagai contoh, apabila kita melakukan penjelajahan dari node 8, kita akan berakhir pada node 5 dengan jalur 8 -> 6 -> 5
Hal tersebut dapat kita manfaatkan untuk melakukan operasi find dan same. Kemudian, untuk menggabungkan 2 himpunan berbeda, kita cukup untuk membuat perwakilan dari suatu himpunan untuk menunjuk kepada perwakilan himpunan lain. Sebagai contoh apabila kita memiliki himpunan {1, 2, 3} dan {6, 7, 8} , seperti pada gambar a. Apabila kita lakukan operasi join maka akan menghasilkan graf seperti pada gambar b
Maka himpunan akan menjadi {1, 2, 3, 6, 7, 8}
Implementasi
Seperti yang telah dijelaskan sebelumnya, bahwa untuk tiap node pada DSU akan menunjuk kepada salah satu node lainnya. Maka dari itu untuk membuat DSU dengan N elemen, kita memerlukan sebuah array untuk menyimpan node apa yang ditunjuk oleh tiap node pada DSU. Kita akan namakan array ini parrent
Inisialisasi
Mula-mula, kita akan membuat array parrent untuk setiap node pada DSU. Kemudian, kita akan membuat semua elemen pada parrent menunjuk kepada dirinya sendiri. Hal ini dikarenakan pada awalnya, semua elemen merupakan merupakan himpunan yang berbeda satu sama lain. Sehingga kita hanya perlu gunakan parent[i] = i untuk setiap indeks i. Berikut implementasinya
int parent[N + 1]; // buat array parent
int main(){
for(int i = 1; i <= N; ++i){ // DSU yang kita pakai adalah 1-index DSU
parent[i] = i; // buat parent dari tiap node adalah dirinya sendiri
}
}
Operasi Find
Seperti yang sudah dijelaskan, operasi find berguna untuk mencari perwakilan dari suatu himpunan. Untuk melakukannya, kita dapat memanfaatkan prinsip rekursif dimana apabila node sekarang adalah perwakilan / akar (ditandai dengan parent dari node itu adalah dirinya sendiri) maka kita akan menggunakan node kita sebagai jawaban. Sedangkan apabila node sekarang bukan perwakilan, maka kita akan melanjutkan rekursi kepada parent dari node sekarang. Operasi ini memilki kompleksitas sebesar O(log N) dimana N adalah banyaknya anggota himpunan. Mengapa log N ?, hal ini dikarenakan semisal untuk tiap node memiliki anak sebanyak 2, maka total jarak suatu node kepada perwakilannya adalah sekitar log N . Berikut adalah contoh implementasinya
int find(int node){
if (parent[node] == node){
/* Apabila node sekarang adalah perwakilan, maka kita
akan mengembalikan nilai node */
return node;
}
else{
/* Melakukan rekursi kepada node parent
apabila node sekarang bukan perwakilan */
return find(parent[node]);
}
}Operasi Same
Untuk memeriksa apakah 2 himpunan merupakan himpunan yang sama, kita hanya perlu memeriksa perwakilan dari kedua himpunan saja. Apabila perwakilan dari kedua himpunan sama, maka dapat dipastikan bahwa kedua himpunan itu sama. Begitupun sebaliknya.
bool same(int a, int b){
// memerika apakah node a dan b memiliki perwakilan yang sama
return find(a) == find(b);
}Operasi Join
Untuk menggabungkan dua himpunan, maka kita cukup mencari perwakilan dari kedua himpunan, lalu membuat salah satu dari kedua perwakilan menunjuk kepada perwakilan yang lain. Berikut adalah implementasinya.
void join(int a, int b){
a = find(a); // mencari perwakilan node a
b = find(b); // mencari perwakilan node b
// buat node a menunjuk node b
parent[a] = b;
}Operasi join memiliki kompleksitas sebanyak O(log N) dikarenakan ia memanggil fungsi find dengan kompleksitas O(log N) sebanyak 2 kali
Optimasi
Terkadang, DSU yang kita buat akan berbentuk garis lurus seperti ini.
Sehingga, apabila kita melakukan pemanggilan find(N) , hal itu akan membuat operasi find akan berjalan sebanyak N kali rekursif dikarenakan kita mengunjungi semua node yang ada selama pencarian perwakilan dari himpunan. Sehingga alih-alih O(log N) , kompleksitas program menjadi menyerupai O (N) . Oleh karena itu, kita perlu suatu cara untuk mempercepat eksekusi DSU yang kita miliki
Path Compression
Salah satu cara untuk mengoptimasi DSU yang kita miliki adalah dengan melakukan kompresi pada setiap path dalam DSU. Sebagai contoh apabila kita memiliki suatu DSU pada gambar [h]
Tampak bahwa apabila kita memanggil find(4) kita akan melakukan rekursi sebanyak 4 kali. Untuk mengoptimalkannya, kita dapat memperpendek panjang path dari node 4 hingga node 1 dengan cara membuat node 4 langsung menunjuk kepada node 1 di akhir fungsi find . Begitu pun dengan semua node yang kita lalui saat melakukan perjalanan dari node 4. Kita akan membuat semua node di dalam path langsung menunjuk kepada node 1. Dengan begitu apabila suatu saat kita memanggil kembali fungsi find(4), maka kompleksitas dari fungsi tersebut menjadi O(1) karena kita dapat langsung menuju kepada node 1 dengan satu langkah. Meskipun secara rata-rata, algoritma ini tetap bekerja dengan kecepatan O(log N) . Sehinnga, DSU akan berubah menjadi seperti gambar [i]
Berikut adalah implementasi dari path compression
int find(int node){
if(parent[node] == node) return node;
else{
// parent dari node sekarang akan menunjuk langsung kepada perwakilan
parent[node] = find(parent[node]);
return parent[node];
}
}Union by Size
Cara kedua yang dapat dilakukan untuk mempercepat DSU yang kita miliki adalah dengan melakukan penggabungan dua himpunan dengan memperhatikan ukuran (banyak node yang ada di masing-masing himpunan) dari tiap himpunan. Secara intuitif, kita menginginkan agar path terpanjang yang ada di DSU kita sependek mungkin. Jika dipikirkan secara greedy, kita dapat mencapai kondisi itu dengan cara membuat perwakilan dari himpunan yang lebih kecil langsung menunjuk kepada perwakilan himpunan yang lebih besar. Mengapa demikian? Karena untuk suatu himpunan yang memiliki ukuran lebih besar, maka kemungkinan besar dia akan memiliki path terpanjang yang lebih panjang pula dari path terpanjang milik himpunan yang lebih kecil. Dengan begitu, kita berharap bahwa path terpanjang yang kita miliki di himpunan baru menjadi sama saja dengan path terpanjang himpunan besar
Berikut adalah implementasi dari Union by Size
int parent[N + 1]; // buat array parent
int size[N + 1]; // untuk menyimpan ukuran suatu himpunan
int main(){
for(int i = 1; i <= N; ++i){ // DSU yang kita pakai adalah 1-index DSU
parent[i] = i; // buat parent dari tiap node adalah dirinya sendiri
size[i] = 1; // ukuran mula-mula tiap himpunan adalah 1
}
}Berikut adalah operasi join yang kita modifikasi sedikit
void join(int a, int b){
a = find(a);
b = find(b);
if(size[a] < size[b]){
/* membuat a selalu menjadi himpunan yang lebih besar dari b,
hal ini untuk kemudahan penulisan program selanjutnya */
swap(a, b);
}
// tambahkan ukuran dari b kepada a
size[a] += size[b];
// buat node b menunjuk kepada a sebagai perwakilan
parent[b] = a;
}Union by Depth
Mirip dengan Union by Size, namun kita akan menggabungkan 2 himpunan berdasarkan kedalaman (panjang path) terpanjang dari 2 himpunan. Apabila kita memiliki 2 himpunan, maka perwakilan dari himpunan dengan kedalaman yang lebih pendek, akan kita buat langsung menunjuk kepada perwakilan dari himpunan dengan kedalaman yang lebih panjang. Dengan begitu, kedalaman dari himpunan baru tidak akan berubah dari kedalaman 2 himpunan sebelumnya. Namun untuk kasus kedalaman kedua himpunan sama, maka kedalaman dari himpunan baru akan memiliki ukuran sama dengan kedalaman dari himpunan lama + 1. Berikut adalah ilustrasinya
Berikut adalah implementasi dari Union by Depth
int parent[N + 1]; // buat array parent
int depth[N + 1]; // untuk menyimpan kedalaman suatu himpunan
int main(){
for(int i = 1; i <= N; ++i){ // DSU yang kita pakai adalah 1-index DSU
parent[i] = i; // buat parent dari tiap node adalah dirinya sendiri
depth[i] = 0; // kedalaman mula-mula tiap himpunan adalah 0
}
}Berikut adalah operasi join yang kita modifikasi sedikit
void join(int a, int b){
a = find(a);
b = find(b);
if(depth[a] < depth[b]){
/* membuat a selalu menjadi himpunan yang memiliki kedalaman maksimal lebih
dari b, hal ini untuk kemudahan penulisan program selanjutnya */
swap(a, b);
}
if(depth[a] == depth[b]){
/* apabila kedalaman mula-mula dari himpunan a, maka kedalaman maksimal dari a
akan bertambah 1 (karena ditambah dari kedalaman maksimal dari b) */
depth[a]++;
}
// buat node b menunjuk kepada a sebagai perwakilan
parent[b] = a;
}Baik Union by Size / Union by Depth akan menghasilkan DSU dengan kompleksitas operasi find dan join masing masing O(log N) . Hal ini tentu sangat baik mengingat kompleksitas O (log N) tergolong cepat.
Kita telah mengenal 3 cara berbeda dalam mengoptimasi DSU yang kita miliki. Dalam penerapannya, ketiga algoritma tadi dapat dikombinasikan satu dengan yang lainnya agar dapat tercapai DSU yang kita inginkan
Last updated