Penerapan algoritma prims

ini salah satu Penerapan algoritma prims bisa diperhatikan sebagai berikut:Misalkan titik menggambarkan vertices dan garis menggambarkan edge dalam sebuah graph, maka algoritma prims melakukan kalkulasi terhadap semua kemungkinan bobot terkecil dari setiap titik.

 

Ini adalah graf berbobot awal. Graf ini bukan pohon karena ada circuit. Nama yang lebih tepat untuk diagram ini adalah graf atau jaringan. Angka-angka dekat garis penghubung adalah bobotnya. Belum ada garis yang ditandai, dan node D dipilih.

Sisi pertama yang akan kita tambahkan ke dalam pohon merentang minimum T adalah sisi yang berbobot minimum dan bersisian dengan simpul D. Dari keempat sisi yang ada, sisi (D,A) berbobot paling kecil yaitu sebesar 5, karena itu sisi tersebut kita tambahkan ke dalam T (ditanda warna biru muda).

Langkah diatas kita ulangi, tetapi kali ini kita mencari sisi berbobot minimum yang bersisian dengan simpul D dan A, yaitu sisi (D,F) yang memiliki besar bobot 6, jadi kita tandai node F dan cabang DF.

Algoritma ini berlanjut seperti di atas. Node B, yang jauhnya 7 dari A, ditandai. Di sini, cabang DB ditandai merah, karena baik node B dan node D telah ditandai hijau, sehingga DB tidak dapat digunakan.

Dalam hal ini, kita dapat memilih antara C, E, dan G. C jauhnya 8 dari B, E 7 dari B, dan G 11 dari F. E yang terdekat, jadi kita tandai node E dan cabang EB. Dua cabang lain ditandai merah, karena kedua node yang terhubung telah digunakan.

Di sini, node yang tersedia adalah C dan G. C jauhnya 5 dari E, dan G 9 dari E. C dipilih, jadi ditandai bersama dengan cabang EC. Cabang BC juga ditandai merah.

Node G adalah satu-satunya yang tersisa. Jauhnya 11 dari F, dan 9 dari E. E lebih dekat, jadi kita tandai cabang EG. Sekarang semua node telah terhubung, dan pohon rentang minimum ditunjukkan dengan warna hijau, bobotnya 39.

Posted in: