My first Magazine pemrograman-kompetitif-dasar | Page 145

11.2 Minimum Spanning Tree
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.23: Tahap 6: Berikutnya kita coba edge h2, 4i. Ternyata menambahkan edge terse-
but akan membentuk siklus. Edge tersebut tidak dijadikan 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.24: Tahap 7: Berikutnya kita coba edge h1, 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.25: Tahap 8: Berikutnya kita coba edge h1, 3i. Ternyata menambahkan edge terse-
but akan membentuk siklus. Edge tersebut tidak dijadikan 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.26: Tahap 9: Semua edge sudah diperiksa, algoritma selesai.
Kompleksitas Kruskal
Bagaimana caranya mengecek apakah dengan menambah suatu edge , akan menciptakan
siklus? Solusi paling sederhana adalah dengan melakukan DFS atau BFS. Karena ada E buah
135