My first Magazine pemrograman-kompetitif-dasar | Page 140

11 Algoritma Graf
solusi dengan cara memilih node satu per satu untuk digabungkan ke tree solusi, hingga seluruh
node masuk ke dalam tree .
Untuk mengimplementasikan algoritma Prim, kita definisikan variabel berikut:
• dist[x]: bobot terkecil yang dapat dipakai untuk menghubungkan node x ke tree .
• visited[x]: bernilai true jika node x sudah masuk ke dalam tree solusi, dan f alse jika belum.
Umumnya, soal MST hanya meminta Anda mencari total bobot dari MST saja. Namun, jika
Anda juga memerlukan edge solusi, maka Anda harus mendefinisikan variabel baru pred[x] yang
menyatakan tetangga dari node x yang menghubungkan x dengan tree solusi. Awalnya kita set
nilai ini dengan −1 karena masih belum diketahui node mana yang menghubungkan x.
Sesuai definisi, pada mulanya seluruh visited[i] bernilai f alse. Selain itu, seluruh node x
memiliki nilai dist[x] = ∞. Kita mulai dengan mengambil sembarang node untuk dijadikan node
pertama dari tree solusi. Untuk memudahkan, Anda dapat memilih node berindeks 1. Khusus
untuk node pertama ini, kita juga set dist-nya menjadi 0. Untuk setiap node u yang mana u baru
saja dimasukkan ke dalam tree solusi, maka kita akan melakukan proses relax sebagai berikut:
dist[v] = min(dist[v], w[u][v]), untuk setiap v ∈ ad j(u) dan visited[v] = f alse
Jika kita mengubah nilai dist[v], maka kita perlu mengubah nilai pred[v] = u, karena edge
dengan bobot terkecil saat ini untuk menghubungkan v adalah dengan melalui u.
Kemudian, proses pemilihan ekspansi tree solusi dilakukan dengan memilih suatu node x
yang mana visited[x] = f alse dan dist[x] minimum. Proses relax akan diulangi lagi hingga seluruh
node masuk ke dalam solusi. Gambar 11.12 sampai Gambar 11.17 mengilustrasikan cara kerja
Prim.
3
6
1
1
2
5
2
3
5
4
4
2
1
dist
0
visited true
pred
−1
2
∞
f alse
−1
3
∞
f alse
−1
4
∞
f alse
−1
5
∞
f alse
−1
Gambar 11.12: Tahap 1: Bentuk awal graf beserta isi tabel dist dan visited. Kita memulai dari
node 1, maka tandai visited[1] = true serta dist[1] = 0.
3
6
1
1
2
5
2
3
5
4
4
2
1
dist
0
visited true
pred
−1
2
∞
f alse
−1
3
6
f alse
1
4
5
f alse
1
5
∞
f alse
−1
Gambar 11.13: Tahap 2: Lakukan proses relax terhadap node 1. Selanjutnya memilih node
yang belum dikunjungi dengan nilai dist terendah untuk ekspansi, yaitu node 4.
Catatan: perubahan nilai pada tabel karena proses relax dicetak dengan warna
biru dan digaris bawah.
130