My first Magazine pemrograman-kompetitif-dasar | Page 146

11 Algoritma Graf
edge yang akan dicek, dan setiap pengecekan memerlukan waktu O(E), maka kompleksitasnya
adalah O(E 2 ).
Agar lebih efisien, kita dapat memanfaatkan struktur data disjoint set . Mula-mula, kita siap-
kan N buah set yang masing-masing berisi satu node pada graf. Suatu edge yang menghubungkan
node x dan y dapat diambil jika x dan y berada pada set yang berbeda. Jika kita mengambil
edge tersebut, kita gabungkan kedua set yang mengandung x dan y. Jika x dan y berada pada
set yang sama, artinya x dan y sudah tergabung pada tree yang sama. Dengan demikian, jika
kita mengambil edge baru yang menghubungkan x dan y, maka dijamin akan menghasilkan siklus.
Maka, kompleksitas akhir Kruskal adalah O(E log E).
implementasi
Algoritma 70 Implementasi algoritma Kruskal dengan optimisasi disjoint set .
1:
2:
3:
4:
5:
6:
7:
8:
9:
10:
11:
function K RUSKAL (edgeList)
INITIALIZE D ISJOINT S ET ()
SORT (edgeList)
for hu, vi ∈ edgeList do
if not CHECK (u, v) then
cost ← cost + w[u][v]
JOIN (u, v)
end if
end for
return cost
end function
. Urutkan berdasarkan bobotnya
Implementasi algoritma Kruskal cukup sederhana, dan dapat dilihat pada Algoritma 70.
136