My first Magazine pemrograman-kompetitif-dasar | Page 144

11 Algoritma Graf
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.19: Tahap 2: Kita coba edge h2, 3i. Karena menambahkan edge tersebut tidak
membentuk siklus, kita ambil sebagai solusi. Untuk kemudahan, solusi ditandai
dengan edge yang dicetak tebal.
3
6
1
2
2
3
5
4
2
edge
bobot
1
4
5
↓
h2, 3i h4, 5i h3, 4i h2, 5i h2, 4i h1, 4i h1, 3i
1
2
2
3
4
5
6
Gambar 11.20: Tahap 3: Berikutnya kita coba edge h4, 5i. Karena menambahkan edge tersebut
tidak membentuk siklus, kita ambil sebagai solusi.
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.21: Tahap 4: Berikutnya kita coba edge h3, 4i. Karena menambahkan edge tersebut
tidak membentuk siklus, kita ambil sebagai solusi.
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.22: Tahap 5: Berikutnya kita coba edge h2, 5i. Ternyata menambahkan edge terse-
but akan membentuk siklus. Edge tersebut tidak dijadikan solusi.
134