Untuk mendapatkan Minumun Spanning Tree, dapat di menggunakan algoritma
1. Algoritma Solin
2. Algoritma Kruskal
Kedua algoritma ini sama-sama, mencari minimum spanning tree ( jarak terpendek ) dengan mencegah graf membentuk sikuit. Perbedaanya, Algoritma Solin mengurutkan bobotnya dari besar ke kecil dan mengeksekusi bobot terbesar terlebih dahulu, Sedangkan algoritma Kruskal pengurutan di lakukan dari bobot terkecil ke besar, dan eksekusi di lakukan dari bobot terkecil.
Untuk lebih jelas, perhatikan contoh berikut ini:
1. ALgoritma Solin
Suatu Graph G, seperti gambar di bawah ini.Ini adalah graf berbobot awal. Graf ini
bukan pohon karena ada sirkuit. Nama yang lebih tepat untuk diagram ini adalah
Graf atau Network.Angka-angka dekat garis penghubung/ruas adalah bobotnya.
Nilai bobot dari Graf tesebut adalah : 86
Kita akan mencari MST dengan menggunakan Algoritma Solin dan Kruskal untuk Graf G
diatas.
Penyeselaian :
a. Urutkan Ruas Graf (G) menurut bobotnya dari bobot yang terbesar sampai bobot
yang terkecil.
Bobot RUAS
15 D,E
9 B,D E,F
8 B,C B,E F,G
7 A,D C,E
6 A,B E,G
5 D,F
b. Lakukan penghapusan masing-masing ruas yang tidak menyebabkan graf menjadi
tidak terhubung atau membentuk sirkuit.
Kita mulai melakukan tahapan penghapusan dengan ruas dengan nilai bobot
terbesar sampai bobot terkecil :
Tahap Penghapusan Selesai, Gambar 6 adalah Minimun Spanning Tree dari Graf G
dengan Nilai Bobot : 56
2. ALgoritma Kruskal
Dengan Graph yang sama, kita akan mencari Minimun Spanning Tree dengan algoritma Kruskal.
1. Mula-mula kita buat Graf G hanya terdiri dari Simpul saja.
2. Urutkan Ruas dari bobot kecil ke besar (DF, AB, EG, AD, CE, BC, BE, FG, BD,
EF,DE), kemudian berdasarkan urutan tersebut, kita menambahkan ruas dengan
mencegah terbentuknya sirkuit.
Sumber : http://allaboutalgoritma.blogspot.com
0 komentar:
Posting Komentar