My first Magazine pemrograman-kompetitif-dasar | Page 142

11 Algoritma Graf
akan masuk ke dalam tree . Dengan demikian, akan ada tepat O(V ) pemilihan node . Jika pemilihan
diimplementasikan secara naif dengan mencari node tersebut secara linear, maka kompleksitas
total pemilihan node adalah O(V 2 ). Pada setiap pemilihan node , terjadi proses relax . Secara
total, setiap edge akan mengalami relax sebanyak 2 kali, sehingga kompleksitas akhir algoritma
Prim adalah O(V 2 + E).
Serupa dengan Dijkstra, kita dapat melakukan optimasi pemilihan edge dengan memanfaat-
kan struktur data heap , sehingga setiap operasi pemilihan edge memiliki kompleksitas O(logV ).
Dengan demikian, kompleksitas total algoritma Prim adalah O((V + E) logV ).
Implementasi
Algoritma 68 Implementasi algoritma Prim dengan optimisasi heap .
1:
2:
3:
4:
5:
6:
7:
8:
function P RIM (s)
cost ← 0
dist ← new integer[V + 1]
visited ← new boolean[V + 1]
pred ← new integer[V + 1]
FILL A RRAY (dist, ∞)
FILL A RRAY (visited, f alse)
FILL A RRAY (pred, −1)
INITIALIZE H EAP ()
9:
. Buat sebuah min-heap
. Masukkan node s dengan jarak tempuh 0 ke dalam heap
10: PUSH (h0, si)
11: dist[s] ← 0
while not IS E MPTY H EAP () do
hcurDist, ui ← POP ()
12:
13:
14:
15:
16:
17:
18:
19:
20:
21:
22:
23:
24:
25:
26:
27:
if not visited[u] then
visited[u] ← true
cost ← cost + dist[u]
. Dapatkan node yang dapat digabungkan ke
tree solusi dengan bobot edge terkecil
. Hanya proses apabila u belum termasuk pada tree solusi
. Tambahkan bobot edge yang menghubungkan
tree solusi terhadap u ke dalam solusi
for v ∈ ad j(u) do
. Lakukan relax untuk semua tetangga u
if (dist[v] > w[u][v]) ∧ (not visited[v]) then
dist[v] = w[u][v]
pred[v] = u
PUSH (hdist[v], vi)
. Masukkan bobot edge dan node yang
end if
diperbaharui ke heap
end for
end if
end while
return cost
end function
Secara implementasi, Algoritma Prim sangat serupa dengan algoritma Dijkstra. Perbedaan
mendasarnya adalah pada setiap pengunjungan node , kita tidak menghitung jarak total dari node
awal, melainkan hanya bobot pada edge -nya saja. Algoritma 69 merupakan prosedur untuk
mencetak edge -edge solusi.
132