Algoritma Kruskal


 Algoritma Kruskal
Halo teman-teman. Hari ini kita belajar bersama yuk, tentang algoritma kruskal. Wah algoritma apalagi tuh? Tanya salah satau teman di ujung sana, ujungnya ujung deh pokoknya. Oke daripada saya juga sok tau nanti jelasinnya, mending kita bahas bareng-bareng aja yuk pake sumber yang terpercaya (GOOGLE maksudnya). Oke selamat belajar!
Algoritma kruskal ini berkaitan dengan mata kuliah saya semester lalu yaitu "Graf & Analisis Algoritma". Algoritma kruskal adalah SALAH SATU algoritma yang digunakan untuk mendapatkan minimum spanning tree dengan weight terkecil.Spanning tree atau dalam bahasa indonesianya yaitu pohon merentang, adalah graf merentang yang yang berupa pohon dan diperoleh dengan cara memutus sirkuit dalam graf. Kalau masih bingung bisa dilihat pada gambar di bawah ini.

Mungkin masih ada yang bingung dengan kata sirkuit. Sirkuit disini maksudnya tidak boleh terbentuk sebuah lintasan atau ruang tertutup.
Perlu juga dicatat bahwa setiap graf terhubung mempunyai paling sedikit satu buah pohon merentang. Kemudian, graf yang tidak mengandung sirkuit adalah pohon merentang itu sendiri. Kemudian (lagi), graf yang sudah mempunyai sirkuit untuk memperoleh pohon merentangnya yaitu dengan cara memutuskan sirkuit yang ada.
Nah sudah bisa ditebak kan, kalau minimum spanning tree itu berarti pohon merentang minimum yang paling penting tentunya dalam pencarian jarak terpendek dalam suatu perjalanan.
Dari beberapa sumber yang ada disebutkan bahwa terdapat 2 algoritma yang digunakan untuk mendapatkan minimum spanning tree. Yaitu yang pertama algoritma PRIM dan yang kedua algoritma KRUSKAL. Nah algoritma yang kedua ini yang sedang kita bicarakan saat ini.
Oke sekarang balik ke algoritma kruskal ya.
Pada algoritma kruskal sisi-sisi yang ada diurutkan terlebih dahulu berdasarkan bobotnya, mulai dari yang terkecil sampai terbesar.
Jadi algoritma kruskal ini digunakan untuk mendapatkan jarak minimum. Jalan-jalan seminimum mungkin yang menghubungkan semua lokasi sehingga setiap lokasi terhubung satu sama lain.