My first Magazine pemrograman-kompetitif-dasar | Page 143

11.2 Minimum Spanning Tree
Algoritma 69 Mencetak edge -edge yang termasuk dalam solusi MST.
1:
2:
3:
4:
5:
6:
7:
procedure PRINT P ATH
for i ← 1, V do
if not pred[i] = −1 then
print pred[i], i
end if
end for
end procedure
II Sekilas Info JJ
Dengan menguasai algoritma Dijkstra terlebih dahulu, Anda akan dapat mempelajari algorit-
ma Prim dengan relatif mudah.
11.2.2
Kruskal
Algoritma Kruskal merupakan algoritma alternatif untuk mencari MST. Kruskal memulai
dengan masing-masing node membentuk tree tersendiri, kemudian menggabungkan tree -tree
tersebut dengan terus menambahkan edge berbobot terkecil, sampai seluruh node pada graf
terhubung dengan sebuah tree .
Diberikan graf dengan V node dan E edge . Mula-mula, urutkan seluruh edge tersebut
berdasarkan bobotnya secara menaik. Kita akan memilih edge -edge untuk ditambahkan sebagai
solusi dari MST, yang pada awalnya masih kosong. Untuk setiap edge e, mulai dari yang memiliki
bobot terkecil: Jika penambahan edge e ke dalam solusi MST tidak membentuk siklus, tambahkan
edge tersebut sebagai solusi MST. Untuk lebih jelasnya, perhatikan contoh pada Gambar 11.18
sampai Gambar 11.26.
3
6
1
1
2
5
2
3
5
4
4
2
edge h2, 3i h4, 5i h3, 4i h2, 5i h2, 4i h1, 4i h1, 3i
bobot
1
2
2
3
4
5
6
Gambar 11.18: Tahap 1: Bentuk awal graf. Kita urutkan edge berdasarkan bobotnya secara
menaik seperti yang tertera pada tabel.
133