Prof. Dra. Kiki Ariyanti Sugeng, M.Si., Ph.D.

Video ini membahas tentang algoritma Kruskal dalam Matematika Diskrit, yang merupakan salah satu metode untuk mencari minimal spanning tree pada graf berbobot. Algoritma ini memilih busur dengan bobot terkecil secara berurutan, memastikan tidak membentuk lingkaran, dan terus menghubungkan simpul-simpul hingga semua terhubung. Dengan contoh penggunaan algoritma Kruskal pada graf berbobot, proses pemilihan busur dilakukan secara sistematis hingga terbentuk spanning tree minimal. Algoritma ini terbukti efektif dalam mencari solusi optimal walaupun ada pilihan busur dengan bobot yang sama.

Algoritma yang biasa dipakai itu adalah algoritma kruskal dan satunya lagi adalah algoritma prim.

Ini algoritma sudah lama tapi sampai sekarang masih bisa dipakai.

Jadi kalau algoritma kruskal misalnya kita punya graf yang seperti ini,

Kita pilih mulai dari yang terkecil bobotnya,

tapi di algoritmanya kita buat suatu himpunan T yang belum ada isinya,

nanti pilihannya itu kita masukkan ke dalam himpunan T.

Sekarang kita pilih suatu busur IJ dengan bobot minimum,

kemudian kita pilih lagi busur IJ dengan bobot minimum berikutnya yang tidak mementuk lingkaran di T,

Kemudian kita teruskan lagi pilih IJ yang lain,

terus dicek di T-nya apakah dia mementuk lingkaran atau tidak.

Jadi kalau kita lakukan di dalam contoh graf ini,

kita lihat di sini langkah pertama kita mulai dari langkah 0,

Langkah pertama kita pilih yang bobotnya terkecil di dalam graf berbobot ini,

jadi kita pilih EC, di sini EC bobotnya adalah 5.

Yang berikutnya kita cari lagi yang minimal kedua,

yang berikutnya lagi yang tidak mementuk lingkaran.

yang berikutnya lagi ada 12 di sini yaitu CF.

karena kita lihat di sini DE kemudian EC dan F sudah nyambung,

Jadi berikutnya lagi kita ambil yang tidak mementuk lingkaran

yang nanti ini kalau dijumlahkan bobotnya akan minimal.

Kalau kita lihat di sini contoh berikutnya,

kita pilih mana bobotnya yang kita ambil,

terus yang paling kecil di sini adalah 1.

Kita boleh memilih antara N1, N2 atau N7, N8.

karena langkah berikutnya kita lihat N1, N2 sama N7, N8

itu kan tidak mementuk lingkaran atau pasirkuit,

Ini langkah ketiga, kita ambil N2, N3 dengan bobot 2.

karena di sini nanti akan mementuk lingkaran.