prim and kruskal algorithm

Kruskal vs Prim

http://www.tulisanku.com

Apakah Kruskal itu?

Adalah salah satu algoritma yang digunakan untuk mendapatkan minimum spanning tree dengan weight terkecil. Menggunakan dua tahap untuk menghasilkan minimum spanning tree yang diinginkan.http://www.tulisanku.com

Tahapan pada Kruskal

Tahap Pertama

Melakukan sorting pada tiap edge mulai dari berat terendah sampai yang paling berat. Membangun sebuah spanning tree dengan menggabungkan semua node menggunakan berat edge yang terendah yang didapatkan dari tahap pertama.

Tahap Kedua

Sebuah edge bisa digunakan jika edge tersebut belum pernah digunakan dan tidak menyebabkan cycle pada spanning tree yang akan dibentuk. http://www.tulisanku.com

Contoh penyelesaian Kruskal(1)

Graph awal yang akan diproses dengan algoritma kruskal



Menghubungkan node dengan melihat weight paling kecil terlebih dahulu

















Apa Prim itu?

Untuk mencari minimum spanning tree untuk graph berbobot yang connected. Pada setiap langkah dipilih vertek yang mempunyai edge dengan bobot minimum dan terhubung dengan minimum spanning tree yang terbentukhttp://www.tulisanku.com

Tahapan Pada Prim

Pilih suatu vertek (V) dari Graf secara bebas. Pilih edge yang memiliki bobot terkecil dan connected dengan V. Tandai vertek tujuan tersebut. Ulangi langkah di atas sampai semua vertek terkunjungi dan tidak ada circuit yang terbentuk dari langkah tersebut.http://www.tulisanku.com

Contoh Penyelesaian Prim (1)




























Terima Kasih


prim and kruskal algorithm

Documents