My first Magazine pemrograman-kompetitif-dasar | Page 115

10.1 Disjoint Set
Inisialisasi Disjoint Set
Inisialisasi disjoint set untuk N elemen dapat dilakukan dengan menyimpan parent dari
masing-masing elemen berupa diri sendiri. Kita dapat menggunakan array untuk menyimpan
parent setiap elemen. Pada Algoritma 48, array par menyimpan indeks elemen yang ditunjuk
sebagai parent dari suatu elemen.
Algoritma 48 Inisialisasi dari disjoint set .
procedure INITIALIZE ()
for i ← 0, N − 1 do
3:
par[i] ← i
4:
end for
5: end procedure
1:
2:
. Indeks elemen dimulai dari 0 (zero-based )
Gambar 10.2: Hasil dari inisialisasi disjoint set . Setiap elemen menunjuk ke dirinya sendiri.
Operasi Join
Ketika kelompok dua elemen perlu digabungkan, ubah parent dari salah satu perwakilan
kelompok ke perwakilan kelompok lainnya.
Perhatikan bahwa yang perlu diubah adalah parent dari perwakilan kelompok suatu elemen,
bukan parent elemen itu sendiri. Hal ini menjamin seluruh elemen pada kelompok tersebut
kini menunjuk pada perwakilan dari kelompok lainnya, yang berarti seluruh elemen pada kedua
kelompok kini menunjuk pada perwakilan kelompok yang sama.
join
Gambar 10.3: Contoh operasi join pada dua elemen dan hasilnya.
Secara sederhana, operasi join dapat dituliskan dalam Algoritma 49.
Algoritma 49 Operasi penggabungan kelompok pada disjoint set .
procedure JOIN (a, b)
repA ← FIND R EPRESENTATIVE (a)
3:
repB ← FIND R EPRESENTATIVE (b)
4:
par[repA] = repB
5: end procedure
1:
2:
105