contoh mencari minimum spanning tree dari graf berbobot dengan algoritma prim
matematika diskrit, Pohon adalah Graf tidak berarah terhubung yang tidak mengandung sirkuit.
Diantara Semua Pohon Pohon Merentang di G, Pohon merentang yang berbobot minimum di namakan pohon merentang minimum (minimum spanning tree) merupakan pohon merentang yang paling penting.
Dan berikut contoh mencari minimum spanning tree dari graf berbobot berikut dengan menggunakan algoritma Prim:
Algoritma Prim :
- Langkah 1 : Ambil Sisi Dari Graf G Yang Berbobot Minimum, Masukan Kedalam Tree (Pohon)
- Langkah 2 : Pilih Sisi (U,V) Yang Mempunyai Bobot Minimal Dan Bersisian Dengan Simpul Di Tree Tetapi (U,V) Tidak Membentuk Sirkuit Di Tree.
- Langkah 3 : Ulangi Langkah 2 Sebanyak N-2 kali.
Jadi Minimum Spanning Tree dari Graf di Atas Adalah : 71
Baca Juga :
Matematika diskrit pewarnaan graf
matematika diskrit lintasan terpendek (shorted path)
Silahkan BAGIKAN lewat faceebook,twitwer,email atau tambahkan ke google plus di bawah ini,"Semoga bermanfaat....,".
ARTIKEL TERKAIT :
programnya mna?
BalasHapustidak ada programnya dhiya.
Hapusmau nanya min, bukannya jalur ke node G lebih kecil lewat node D ya? kenapa malah lewat node H ya?
BalasHapusatau aku salah pemahaman, bantu ya :D
mau nanya min, bukannya jalur ke node G lebih kecil lewat node D ya? kenapa malah lewat node H ya?
BalasHapusatau aku salah pemahaman, bantu ya :D
mau nanya min, bukannya jalur ke node G lebih kecil lewat node D ya? kenapa malah lewat node H ya?
BalasHapusatau aku salah pemahaman, bantu ya :D
Jawaban salah, tolong dicek dulu
BalasHapus{(A,C),(C,D),(D,G),(G,H),(H,G),(G,B),(G,F)} bobot 67
BalasHapus