My first Magazine pemrograman-kompetitif-dasar | Page 116

10 Struktur Data NonLinear
Operasi findRepresentative
Fungsi FIND R EPRESENTATIVE (x) mengembalikan elemen perwakilan dari kelompok tempat
elemen x berada. Fungsi FIND R EPRESENTATIVE (x) dapat diimplementasikan secara rekursif, yaitu
dengan menelusuri parent dari suatu elemen sampai ditemukan elemen yang memiliki parent
berupa dirinya sendiri, seperti yang ditunjukkan pada Algoritma 50.
Algoritma 50 Pencarian perwakilan kelompok dari suatu elemen x.
1:
2:
3:
4:
5:
6:
7:
function FIND R EPRESENTATIVE (x)
if par[x] = x then
return x
else
return FIND R EPRESENTATIVE (par[x])
end if
end function
Fungsi FIND R EPRESENTATIVE memiliki kekurangan yaitu kompleksitasnya sebesar O(L), de-
ngan L adalah panjangnya jalur dari elemen x sampai elemen perwakilan kelompoknya. Ketika
L mendekati N, fungsi ini tidak efisien bila dipanggil berkali-kali. Oleh karena itu kita dapat
menerapkan teknik path compression, yaitu mengubah nilai parent dari setiap elemen yang dilalui
langsung ke elemen perwakilan kelompok. Hal ini menjamin untuk pemanggilan FIND R EPRESEN -
TATIVE berikutnya pada elemen yang bersangkutan bekerja secara lebih efisien.
L
x
(a)
x
(b)
Gambar 10.4: Gambar (a) menunjukkan contoh pemanggilan FIND R EPRESENTATIVE pada elemen
x, yang membutuhkan kompleksitas sebesar O(L). Gambar (b) menunjukkan hasil
path compression sesudah pemanggilan FIND R EPRESENTATIVE .
Implementasi dari path compression cukup dilakukan dengan menambahkan pencatatan
elemen perwakilan kelompok untuk setiap elemen yang dilalui.
106