Graph & Tree
Dalam istilah ilmu komputer, sebuah struktur data adalah cara penyimpanan, pengorganisasian dan pengaturan data di dalam media penyimpanan komputer sehingga data tersebut dapat digunakan secara efisien. Dalam teknik pemrograman, struktur data berarti tata letak data yang berisi kolom-kolom data, baik itu kolom yang tampak oleh pengguna (user) ataupun kolom yang hanya digunakan untuk keperluan pemrograman yang tidak tampak oleh pengguna.
Graph
Graph merupakan struktur data yang paling umum. Jika struktur linear memungkinkan pendefinisian keterhubungan sekuensial antara entitas data, struktur data tree memungkinkan pendefinisian keterhubungan hierarkis, maka struktur graph memungkinkan pendefinisian keterhubungan tak terbatas antara entitas data.
Representasi data dengan struktur data linear ataupun hirarkis pada masalah ini masih bisa digunakan namun akan membutuhkan pencarian-pencarian yang kurang efisien. Struktur data graph secara eksplisit menyatakan keterhubungan ini sehingga pencariannya langsung (straight forward) dilakukan pada strukturnya sendiri.
Tree
Tree merupakan salah satu bentuk struktur data tidak linear yang menggambarkan hubungan yang bersifat hirarkis (hubungan one to many) antara elemen-elemen. Tree bisa didefinisikan sebagai kumpulan simpul/node dengan satu elemen khusus yang disebut Root dan node lainnya. Tree juga adalah suatu graph yang acyclic, simple, connected yang tidak mengandung loop.
Struktur data bst sangat penting dalam struktur pencarian, misalkan dalam kasus pencarian dalam sebuah list, jika list sudah dalam keadaan terurut maka proses pencarian akan semakin cepat, jika kita menggunakan list contigue dan melakukan pencarian biner
Hubungan Graph & Tree dengan Pemograman
Dalam mendalami sebuah algoritma yang menjadi landasan untuk mengembangkan suatu program atau aplikasi, hal ini merupakan metode yang berguna untuk menyelesaikan dan memahami suatu masalah yang bersangkutan dengan seksama. Karena masalah bisa diseselsaikan secara efinisan dalam waktu yang singkat menggunakan algoritma-algoritma tersebut sehingga bisa menjadi mekanisme mengimplementasikan perancangan dan analisi suatu pemograman secara terstruktur dengan baik. Selain itu, mampu menganalisa suatu perancangan yang sulit jadi lebih mudah untuk banyak pengguna atau user.
Algoritma Kruskal adalah algoritma untuk mencari pohon merentang minimum secara langsung didasarkan pada algoritma MST (Minimum Spanning Tree) umum. Pada algoritma Kruskal sisi-sisi di dalam graf diurut terlebih dahulu berdasarkan bobotnya dari kecil ke besar. Sisi yang dimasukkan ke dalam himpunan T adalah sisi graf G sedemikian sehingga T adalah pohon. Pada keadaan awal, sisi-sisi sudah diurut berdasarkan bobot membentuk hutan (forest). Hutan tersebut dinamakan hutan merentang (spanning forest). Sisi dari graf G ditambahkan ke T jika tidak membentuk sirkuit di T.
Perbedaan prinsip antara algoritma Prim dan Kruskal adalah jika pada algoritma Prim sisi yang dimasukkan ke dalam T harus bersisian dengan sebuah simpul di T, maka pada algoritma Kruskal sisi yang dipilih tidak perlu bersisian dengan simpul di T asalkan penambahan sisi tersebut tidak membentuk sirkuit.
Langkah-langkah dalam algoritma Kruskal adalah sebagai berikut:
1. Lakukan pengurutan terhadap setiap sisi di graf mulai dari sisi dengan bobot terkecil sampai terbesar.
2. Pilih sisi yang mempunyai bobot minimum yang tidak membentuk sirkuit di pohon. Tambahkan sisi tersebut ke dalam pohon.
3. Ulangi langkah 2 sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon merentang minimum berjumlah n-1 (n adalah jumlah simpul di graf).
Contoh kasus yang menggunakan algoritma Kruskal
Memecahkan sebuah konsep masalah pada Indomaret yaitu menggunakan Algoritma Kruskal dalam pendistribusian barang dan produk, dengan asumsi tiap Indomaret adalah sebuah simpul (node) dan jalan adalah garis (edge). Konsep tersebut diterapkan pada pohon merentang minimum dengan mencari jalur terpendek dari sebuah jalan sehingga diawali dengan mencari bobot yang kecil. Jaringan distribusi barang dan produk yang telah dikirim oleh Indomaret menggunakan metode Algoritma Kruskal. Hasil dari aplikasi jaringan distribusi barang dan produk dengan menggunakan metode Algoritma Kruskal dapat menganalisis jaringan Indomaret dengan meminimalisasi jarak antar Indomaret ke Indomaret. Selanjutnya sehingga lebih optimal dalam pengiriman barang dan produk sehingga jarak yang ditempuh lebih singkat.
Contoh Program:
#include <cstdlib>
#include <iostream>
#include <fstream>
using namespace std;
class kruskal
{
private:
int n ;
int noe;
int graph_edge[100][4];
int tree[10][10];
int sets[100][10];
int top[100];
public:
int read_graph();
void initialize_span_t();
void sort_edges();
void algorithm();
int find_node(int );
void print_min_span_t();
};
int kruskal::read_graph()
{
cout << "----------------------------------------------------------------" <<endl;
cout << " KELOMPOK 5 " <<endl;
cout << " PROGRAM ALGORITMA KRUSKAL INDOMARET DI KABUPATEN TANAH LAUT " <<endl;
cout << "----------------------------------------------------------------" <<endl;
cout<<endl;
cout << " Banyak titik graph : "; cin >> n;
noe=0;
cout<<"\n Jarak antar tiap titik:\n";
for(int i=1;i<=n;i++)
{
for(int j=i+1;j<=n;j++)
{
cout << " ("<<i<<" , "<<j<<") = ";
float w;
cin>>w;
if(w!=0)
{
noe++;
graph_edge[noe][1]=i;
graph_edge[noe][2]=j;
graph_edge[noe][3]=w;
}
}
}
}
void kruskal::sort_edges()
{
for(int i=1;i<=noe-1;i++)
{
for(int j=1;j<=noe-i;j++)
{
if(graph_edge[j][3]>graph_edge[j+1][3])
{
int t=graph_edge[j][1];
graph_edge[j][1]=graph_edge[j+1][1];
graph_edge[j+1][1]=t;
t=graph_edge[j][2];
graph_edge[j][2]=graph_edge[j+1][2];
graph_edge[j+1][2]=t;
t=graph_edge[j][3];
graph_edge[j][3]=graph_edge[j+1][3];
graph_edge[j+1][3]=t;
}
}
}
cout<<"\n\n Setelah Jarak diurutkan adalah ::\n";
for(int i=1;i<=noe;i++)
cout << " (" << graph_edge[i][1] << " , "<<graph_edge[i][2] << " ) = " <<graph_edge[i][3]<<endl;
}
void kruskal::algorithm()
{
for(int i=1;i<=n;i++)
{
sets[i][1]=i;
top[i]=1;
}
cout<<"\n Rentang Yang di Pakai\n\n";
for(int i=1;i<=noe;i++)
{
int p1=find_node(graph_edge[i][1]);
int p2=find_node(graph_edge[i][2]);
if(p1!=p2)
{
cout<<"Rentang yg masuk ke pohon ::"
<<" < "<<graph_edge[i][1]<<" , "
<<graph_edge[i][2]<<" > "<<endl<<endl;
tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];
// Mix the two sets
for(int j=1;j<=top[p2];j++)
{
top[p1]++;
sets[p1][top[p1]]=sets[p2][j];
}
top[p2]=0;
}
else
{
cout<<"Jika "
<<" < "<<graph_edge[i][1]<<" , "
<<graph_edge[i][2]<<" > "<<"di masukkan, maka terbentuk siklus. jadi di hapus\n\n";
}
}
}
int kruskal::find_node(int n)
{
for(int i=1;i<=noe;i++)
{
for(int j=1;j<=top[i];j++)
{
if(n==sets[i][j])
return i;
}
}
return -1;
}
int main(int argc, char *argv[])
{
kruskal obj;
obj.read_graph();
obj.sort_edges();
obj.algorithm();
system("PAUSE");
return EXIT_SUCCESS;
}
Algoritma Dijkstra
Algoritma Dijkstra, (penemunya adalah seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graph berarah dengan bobot-bobot sisi yang bernilai positif.
Algoritma Dijkstra, (penemunya adalah seorang ilmuwan komputer, Edsger Dijkstra), adalah sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek untuk sebuah graph berarah dengan bobot-bobot sisi yang bernilai positif.
Tujan Algoritma Dijkstra
1. Tujuan Algoritma Dijkstra yaitu untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya.
2. Kelemahan algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses.
3. Jumlah titik menentukan tingkat efektifitas dari algoritma djikstra.
Urutan Logika Algoritma Dijkstra
1. Beri nilai bobot (jarak) untuk setiap titik ke titik lainnya, lalu set nilai 0 pada node awal dan nilai tak hingga terhadap node lain (yang belum terisi).
2. Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.
3. Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan.
4. Setelah selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.
5. Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.
2. Set semua node “Belum terjamah” dan set node awal sebagai “Node keberangkatan”.
3. Dari node keberangkatan, pertimbangkan node tetangga yang belum terjamah dan hitung jaraknya dari titik keberangkatan.
4. Setelah selesai mempertimbangkan setiap jarak terhadap node tetangga, tandai node yang telah terjamah sebagai “Node terjamah”. Node terjamah tidak akan pernah di cek kembali, jarak yang disimpan adalah jarak terakhir dan yang paling minimal bobotnya.
5. Set “Node belum terjamah” dengan jarak terkecil (dari node keberangkatan) sebagai “Node Keberangkatan” selanjutnya dan lanjutkan dengan kembali ke step 3.
Contoh Program:
#include <iostream>
#define INF 99999
using namespace std;
main()
{
int n=10,i,j,start;
//cout<<"Masukan Jumlah Vertex : ";
//cin>>n;
int G[n][n],tempGraf[n][n],jarak[n],visit[n],temp[n],count;
G[0][0]=0; G[0][1]=4; G[0][2]=4; G[0][3]=3; G[0][4]=0; G[0][5]=0; G[0][6]=0; G[0][7]=0; G[0][8]=0; G[0][9]=0;
G[1][0]=4; G[1][1]=0; G[1][2]=1; G[1][3]=0; G[1][4]=0; G[1][5]=2; G[1][6]=5; G[1][7]=0; G[1][8]=0; G[1][9]=0;
G[2][0]=4; G[2][1]=1; G[2][2]=0; G[2][3]=1; G[2][4]=2; G[2][5]=0; G[2][6]=0; G[2][7]=0; G[2][8]=0; G[2][9]=0;
G[3][0]=3; G[3][1]=0; G[3][2]=1; G[3][3]=0; G[3][4]=1; G[3][5]=0; G[3][6]=0; G[3][7]=0; G[3][8]=0; G[3][9]=0;
G[4][0]=0; G[4][1]=0; G[4][2]=2; G[4][3]=1; G[4][4]=0; G[4][5]=1; G[4][6]=0; G[4][7]=0; G[4][8]=5; G[4][9]=0;
G[5][0]=0; G[5][1]=0; G[5][2]=2; G[5][3]=0; G[5][4]=0; G[5][5]=0; G[5][6]=2; G[5][7]=4; G[5][8]=0; G[5][9]=0;
G[6][0]=0; G[6][1]=2; G[6][2]=0; G[6][3]=0; G[6][4]=0; G[6][5]=2; G[6][6]=0; G[6][7]=1; G[6][8]=0; G[6][9]=4;
G[7][0]=0; G[7][1]=0; G[7][2]=0; G[7][3]=0; G[7][4]=0; G[7][5]=4; G[7][6]=1; G[7][7]=0; G[7][8]=2; G[7][9]=1;
G[8][0]=0; G[8][1]=0; G[8][2]=0; G[8][3]=5; G[8][4]=5; G[8][5]=0; G[8][6]=0; G[8][7]=2; G[8][8]=2; G[8][9]=1;
G[9][0]=0; G[9][1]=0; G[9][2]=0; G[9][3]=0; G[9][4]=0; G[9][5]=0; G[9][6]=4; G[9][7]=1; G[9][8]=2; G[9][9]=0;
for(i = 0;i < n ;i++)
{
for (j=0;j<n;j++)
{
cout<<"Matriks "<<"["<<i<<"]"<<"["<<j<<"]"<<" : ";
cout<<G[i][j]<<endl;
}
}
/*cout<<"Masukan Matrix Graf : \n";
for(i = 0;i < n ;i++)
{
for (j=0;j<n;j++)
{
cout<<"Matriks "<<"["<<i<<"]"<<"["<<j<<"]"<<" : ";
cin>>G[i][j];
}
}*/
cout<<"Masukan Vertex Asal : ";
cin>>start;
for(i=0;i<n;i++)
{
for (j=0;j<n;j++)
{
if (G[i][j] == 0)
{
tempGraf[i][j] = INF;
}
else{
tempGraf[i][j] = G[i][j];
}
}
}
for (i = 0;i<n;i++)
{
jarak[i] = tempGraf[start][i];
temp[i] = start;
visit[i] = 0;
}
jarak[start] = 0;
visit[start] = 1;
count =1; ///dimulai dari 1 karena kita tidak akan menghitung vertex asal lagi
///proses untuk menghitung vertex yang dikunjungi
int jarakmin,nextvertex;
while (count < n-1)
{
jarakmin = INF;
for (i=0;i<n;i++)
{
///jika jarak lebih kecil dari jarak minimum dan vertex belum dikunjungi
/// maka jarak minimum adalah jarak yang sudah dibandingkan sebelumnya dengan jarakmin
if(jarak[i] < jarakmin && visit[i]!=1)
{
jarakmin = jarak[i];
nextvertex = i; //untuk memberikan vertex pada jarak minimum
}
}
/// untuk mengecek vertex selanjutnya yang terhubung dengan vertex lain yang memiliki jarak minimum
visit[nextvertex] = 1;
for(i = 0;i<n;i++)
{
if(visit[i]!=1)
{
if(jarakmin+tempGraf[nextvertex][i]<jarak[i])
{
jarak[i] = jarakmin+tempGraf[nextvertex][i];
temp[i] = nextvertex;
}
}
}
count++;
}
///nenampilkan jalur dan jarak untuk setiap vertex
int a[n+1],k;
for (i = 0; i < n ;i++)
{
if(i!=start)
{
cout<<"\nHasil jarak untuk vertex ke-"<<i<<" adalah\n"<<jarak[i];
j=i;
cout<<"<-"<<i;
while(j!=start)
{
j=temp[j];
cout<<j;
if(j!=start)
{
cout<<"<-";
}
}
}
}
cout<<"\nTotal Jaraknya adalah "<<jarak[n-1];
return 0;
}
0 komentar:
Posting Komentar