Home

 

 

 

 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.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s