My first Magazine pemrograman-kompetitif-dasar | Page 114

10 Struktur Data NonLinear
dari kadang a ke kandang b, seluruh kandang yang terhubung dengan kandang a kini terhubung
dengan seluruh kandang yang terhubung dengan kandang b. Operasi ini dapat dipandang sebagai
operasi penggabungan himpunan. Sementara itu, pemeriksaan apakah sepasang kandang ter-
hubung dapat dilakukan dengan memeriksa apakah kedua kandang berada pada himpunan yang
sama.
Sebagai contoh, misalkan N = 5. Kondisi himpunan pada awalnya adalah {1}, {2}, {3}, {4}, {5}.
Berikut contoh operasi-operasi secara berurutan dan perilaku yang diharapkan:
1.
2.
3.
4.
5.
6.
7.
join(1, 4), kini himpunan yang ada adalah {1, 4}, {2}, {3}, {5}.
check(1, 2): laporkan bahwa 1 dan 2 berada di kelompok berbeda.
join(1, 2), kini kelompok yang ada adalah {1, 2, 4}, {3}, {5}.
check(1, 2): laporkan bahwa 1 dan 2 berada di kelompok yang sama.
join(3, 5), kini kelompok yang ada adalah {1, 2, 4}, {3, 5}.
join(2, 3), kini kelompok yang ada adalah {1, 2, 3, 4, 5}.
check(1, 5): laporkan bahwa 1 dan 5 berada di kelompok yang sama.
Solusi yang dapat digunakan adalah dengan merepresentasikan setiap kandang sebagai node
seperti dalam konsep graf. Operasi join dapat dianggap sebagai penambahan edge . Sedangkan
untuk setiap operasi check, diperlukan penjelajahan graf untuk memeriksa apakah kedua node
terhubung. Representasi graf yang paling efisien dalam permasalahan ini adalah adjacency list .
Kompleksitas check adalah O(N 2 ) apabila penjelajahan graf dilakukan secara naif dan seluruh
kemungkinan edge dilalui. Solusi sederhana ini tidak efisien ketika banyak dilakukan operasi
check(a,b). Oleh karena itu diperlukan sebuah struktur data efisien yang dapat menyelesaikan
permasalahan ini.
10.1.1
Konsep Disjoint Set
Ide dasar untuk menyelesaikan permasalahan tersebut adalah: untuk setiap kelompok
yang ada, pilih suatu elemen sebagai perwakilan kelompok. Perlu diperhatikan untuk setiap
elemen perlu mengetahui siapa perwakilan kelompoknya. Untuk memeriksa apakah dua elemen
berada pada kelompok yang sama, periksa apakah perwakilan kelompok mereka sama. Untuk
menggabungkan kelompok dari dua elemen, salah satu perwakilan kelompok elemen perlu
diwakilkan oleh perwakilan kelompok elemen lainnya.
Setiap elemen perlu menyimpan pointer ke elemen yang merupakan perwakilannya. Pointer
yang ditunjuk oleh suatu perwakilan kelompok adalah dirinya sendiri. Karena pada awalnya
setiap elemen membentuk kelompoknya sendiri, maka awalnya setiap pointer ini menunjuk pada
dirinya sendiri. Untuk mempermudah, mari kita sebut pointer ini sebagai parent.
Gambar 10.1: Ilustrasi dua kelompok elemen berikut parent dari masing-masing elemen pada
disjoint set.
104