10 April 2011

Pemodelan Sistem : Minumun Spanning Tree dengan Algoritma Solin dan Algoritma Kruskal

10 April 2011
Apabila G suatu graf berbobot (suatu Network), maka Minimun Spanning Tree dari G adalah Spanning Tree dengan jumlah bobot terkecil.

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.








Untuk contoh Penerapan algoritma kruskal bisa di download di sini:
(untuk sementara linknya belum ada, belum di upload hehehhe :D) mungkin besok saya upload, dah ngantuk.

5 comments:

Anonim mengatakan...

:h: :a: :n: :s:

arul mengatakan...

mw nanya apa yang salah dengan code ini?
#include
#include

typedef struct Node{
int data;
Node *kiri;
Node *kanan;
}
Void tambah(Node **root,int databaru){
if((*root) == NULL){
Node *baru;
baru = new Node;
baru->data = databaru;
baru->kiri = NULL;
baru->kanan = NULL;
(*root) = baru;
(*root)->kiri = NULL;
(*root)->kanan = NULL;
printf("Data bertambah!");
}
else if(databaru < (*root)->data)
tambah(&(*root)->kiri,databaru);
else if(databaru > (*root)->data)
tambah(&(*root)->kanan,databaru);
else if(databaru == (*root)->data)
printf("Data sudah ada!");
}
void preOrder(Node *root){
if(root != NULL){
printf("%d ",root->data);
preOrder(root->kiri);
preOrder(root->kanan);
}
}
void inOrder(Node *root){
if(root != NULL){
inOrder(root->kiri);
printf("%d ",root->data);
inOrder(root->kanan);
}
}
void postOrder(Node *root){
if(root != NULL){
postOrder(root->kiri);
postOrder(root->kanan);
printf("%d ",root->data);
}
}
void main(){
int pil,c;
Node *pohon,*t;
pohon = NULL;
do{
clrscr();
int data;
printf("MENU\n");
printf("1. Tambah\n");
printf("2. Lihat pre-order\n");
printf("3. Lihat in-order\n");
printf("4. Lihat post-order\n");
printf("5. Exit\n");
printf("Pilihan : "); scanf("%d",&pil);
switch(pil){
case 1: printf("Data baru : ");scanf("%d",&data);
tambah(&pohon,data);
break;
case 2: if(pohon!=NULL) preOrder(pohon);else printf("Masih kosong!");
break;
case 3: if(pohon!=NULL) inOrder(pohon);else printf("Masih kosong!");
break;
case 4: if(pohon!=NULL) postOrder(pohon);else printf("Masih kosong!");
break;
}
getch();
}while(pil!=5);
}

Anonim mengatakan...

:b:

Fikri_Blog mengatakan...

gan link download nya mana ??? saya butuh banget reference nya.,.thanks

Andrian Bone Prasetyo mengatakan...
Komentar ini telah dihapus oleh pengarang.

Poskan Komentar

sampaikan komentar dengan sopan dan bertanggung jawab :)