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 



Tahap Kedua 



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.

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

http://www.tulisanku.com

Contoh penyelesaian Kruskal(2)

Menghubungkan node dengan melihat weight paling kecil terlebih dahulu

http://www.tulisanku.com

Contoh penyelesaian Kruskal(3)

Menghubungkan node dengan melihat weight paling kecil terlebih dahulu

http://www.tulisanku.com

Contoh penyelesaian Kruskal(4)

Menghubungkan node dengan melihat weight paling kecil terlebih dahulu

http://www.tulisanku.com

Contoh penyelesaian Kruskal(5)

Menghubungkan node dengan melihat weight paling kecil terlebih dahulu

http://www.tulisanku.com

Contoh penyelesaian Kruskal(6)

Menghubungkan node dengan melihat weight paling kecil terlebih dahulu

http://www.tulisanku.com

Contoh penyelesaian Kruskal(7)

Menghubungkan node dengan melihat weight paling kecil terlebih dahulu

http://www.tulisanku.com

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 terbentuk http://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)

http://www.tulisanku.com

Contoh Penyelesaian Prim (2)

http://www.tulisanku.com

Contoh Penyelesaian Prim (3)

http://www.tulisanku.com

Contoh Penyelesaian Prim (4)

http://www.tulisanku.com

Contoh Penyelesaian Prim (5)

http://www.tulisanku.com

Contoh Penyelesaian Prim (6)

http://www.tulisanku.com

Contoh Penyelesaian Prim (7)

http://www.tulisanku.com

Contoh Penyelesaian Prim (8)

http://www.tulisanku.com

Contoh Penyelesaian Prim (9)

http://www.tulisanku.com

Contoh Penyelesaian Prim (10)

http://www.tulisanku.com

Contoh Penyelesaian Prim (11)

http://www.tulisanku.com

Contoh Penyelesaian Prim (12)

http://www.tulisanku.com

Contoh Penyelesaian Prim (13)

http://www.tulisanku.com

Contoh Penyelesaian Prim (14)

http://www.tulisanku.com

Terima Kasih

http://www.tulisanku.com