Algoritma Pemrograman2 "Graph dan Tree"

 A. GRAF

Sebuah graf G didefinisikan sebagai pasangan himpunan (V,E) , dengan V adalah himpunan tak kosong dari simpul-simpul (vertices) pada G. Sedangkan E adalah himpunan rusuk (edge) pada G yang menghubungkan sepasang simpul. Himpunan simpul pada G dinotasikan sebagai V, dan himpunan rusuk pada G dinotasikan sebagai E. Jadi G=(V,E) (Harju, 2012:4).

B. POHON (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.

C. ALGORITMA KRUSKAL
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).

Kelebihan dan kekurangan algoritma kruskal :
a.     Kelebihan : Sangat cocok digunakan saat graf memiliki sisi berjumlah sedikit namun memiliki sangat banyak simpul, karena orientasi kerja algoritma ini adalah berdasarkan urutan bobot sisi bukan simpul.
b.       Kekurangan : kurang cocok digunakan saat graf dimana setiap simpul terhubungkan dengan semua simpul yang lain. Karena algoritma ini menitik beratkan pada pencarian sisi yang diurutkan.

 Contoh kasus Algoritma Kruskal :
Memecahkan sebuah konsep masalah pada PT. PLN yaitu menggunakan Algoritma Kruskal dalam pendistribusian listrik, dengan asumsi tiap rumah adalah sebuah simpul (node) dan kabel listrik adalah garis (edge). Konsep tersebut diterapkan pada pohon merentang minimum dengan mencari jalur terpendek dari sebuah kabel listrik sehingga diawali dengan mencari bobot yang kecil. Dengan membandingkan jaringan distribusi listrik yang telah dipasang oleh PT. PLN dengan jaringan distribusi listrik menggunakan metode Algoritma Kruskal. Hasil dari aplikasi jaringan distribusi listrik dengan menggunakan metode Algoritma Kruskal dapat menganalisis jaringan PT. PLN dengan meminimalisasi panjang kabel listrik sehingga lebih optimal dalam pemasangannya dan tidak ada pasokan kabel listrik yang terbuang percuma.

Contoh Algoritma Pemrograman :

#include <cstdlib> #include <iostream> #include <fstream> using namespace std;   class kruskal    {  private:        int n ;//no of nodes        int noe; //no edges in the graph        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()    {    /** Sort the edges using bubble sort in increasing order******/        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;                        }

Matrik Ketetanggan :

Running Kruskal :

         D.  ALGORITMA DJIKSTRA

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

     •     Tujuan Algoritma Dijkstra yaitu untuk menemukan jalur terpendek berdasarkan bobot terkecil dari satu titik ke titik lainnya.

•     Kelemahan algoritma ini adalah semakin banyak titik akan semakin memakan waktu proses.

•     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 step3.

Contoh kasus Algoritma Djikstra:

Kebun Raya Purwodadi memiliki luas mencapai 85 hektar. Kebun raya purwodadi memiliki koleksi tanaman sejumlah 2002 jenis/spesies, 178 suku/family, 962 marga/genus dan 11.669 specimen. Dengan jumlah tanaman yang begitu banyak, dibutuhkan aplikasi yang dapat menunjukkan jalan dari lokasi pengguna ke lokasi tanaman yang dituju. Dalam pembuatan aplikasi, dibutuhkan suatu metode/algoritma untuk melakukan perhitungan guna mendapatkan jarak terdekat. Algoritma yang digunakan pada penelitian ini menggunakan algortima dijkstra yang dipilih karena memiliki waktu running time lebih cepat dibandingkan algoritma Bellman-Ford. Untuk merancang aplikasi yang dibutuhkan, tahap identifikasi kebutuhan fungsional berdasarkan kebutuhan dari pengunjung kebun raya. Sedangkan untuk kebutuhan non-fungsional adalah tentang usability dan compatibility. Implementasi yang dibuat berdasarkan perancangan yang telah dibuat sebelumnya. Web server dibangun menggunakan bahasa PHP, sedangkan aplikasi android menggunakan bahasa Java dengan tools android studio. Pada pengujiannya dilakukan secara black-box untuk menguji fungsional dari aplikasi dan semuanya valid. Sedangkan pengujian white-box digunakan untuk menguji algoritma dijkstra yang digunakan. Selain itu dilakukan pengujian usability dan menunjukkan hasil yang memuaskan dengan presentase sebesar 70.916% dengan jumlah responden sebanyak 30 orang.

Contoh Pemrograman Algoritma Djikstra :

#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; }

Hasil Running Dijkstra :

Matrik Ketetangaan : 

Hasil Graph Melintang :

Kesimpulan : 

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.

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.

 Berdasarkan penelitian yang telah dilakukan, dapat disimpulkan bahwa program algoritma djikstra maupun algoritma kruskal sangat membantu didalam menemukan data berupa jarak yang terdekat sehingga dapat menambah efisiensi waktu dalam pencarian tempat yang terdekat yang akan dituju. Dari kedua program ini, algoritma kruskal lebih unggul daripada algoritma djikstra, karena didalam algoritma kruskal tidak terjadi penginputan yang berulang (prinsipnya misalkan 1,2 = 2,1), sedangkan program algoritma djikstra selalu melakukan penginputan yang berulang (prinsipnya misalkan 1,2 ≠ 2,1). Dengan adanya prinsip seperti ini, tentu sangat mempengaruhi dalam waktu untuk pencarian data berupa jarak yang terdekat. 

Daftar Pustaka

 ///https://medium.com/@muhamadenrinal/minimum-spanning-tree-dengan-algoritma-prim-dan-kruskal-4aa9fd2b075
       ///http://lukmanreza.blogspot.com/2012/05/program-c-algoritma-kruskal.html