My first Magazine pemrograman-kompetitif-dasar | Page 141

11.2 Minimum Spanning Tree
3
6
1
1
2
5
2
3
5
4
4
2
1
dist
0
visited true
pred
−1
2
4
f alse
4
3
4
2
5
f alse true
4
1
5
2
f alse
4
Gambar 11.14: Tahap 3: Lakukan proses relax terhadap node 4. Selanjutnya memilih node
yang belum dikunjungi dengan nilai dist terendah untuk ekspansi. Ada 2 kandidat,
kita bebas memilih yang mana saja. Misal kita pilih node 3.
3
6
1
1
2
5
2
3
5
4
4
2
1
dist
0
visited true
pred
−1
2
3
4
1
2
5
f alse true true
3
4
1
5
2
f alse
4
Gambar 11.15: Tahap 4: Lakukan proses relax terhadap node 3. Selanjutnya memilih node
yang belum dikunjungi dengan nilai dist terendah untuk ekspansi, yaitu node 2.
3
6
1
1
2
5
2
3
5
4
4
2
1
2
3
4
dist
0
1
2
5
visited true true true true
pred
−1
3
4
1
5
2
f alse
4
Gambar 11.16: Tahap 5: Lakukan proses relax terhadap node 2. Selanjutnya memilih node
yang belum dikunjungi dengan nilai dist terendah untuk ekspansi, yaitu node 5.
3
6
1
1
2
5
2
3
5
4
4
2
1
2
3
4
5
dist
0
1
2
5
2
visited true true true true true
pred
−1
3
4
1
4
Gambar 11.17: Tahap 6: Lakukan proses relax terhadap node 5. Karena semua nilai pada
visited sudah true, maka algoritma selesai.
Setelah menjalankan algoritma Prim, kita dapat mengetahui total bobot dari MST dengan
menghitung total nilai pada tabel dist. Pada kasus ini, total bobotnya adalah 10. Untuk men-
dapatkan edge -edge solusi MST, cukup lihat tabel pred. Untuk setiap node u, jika nilai pred[u]
tidaklah −1, maka edge hu, pred[u]i masuk dalam solusi MST. Pada kasus ini, edge yang masuk
dalam solusi MST adalah [h1, 3i, h2, 4i, h5, 1i, h2, 4i].
Kompleksitas Prim
Mari kita analisa kompleksitas algoritma Prim. Pada mulanya, semua node kecuali node
awal tidak termasuk di dalam tree . Pada setiap iterasi pemilihan node , tepat satu buah node
131