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 :
1. ///https://medium.com/@muhamadenrinal/minimum-spanning-tree-dengan-algoritma-prim-dan-kruskal-4aa9fd2b075
2. ///http://lukmanreza.blogspot.com/2012/05/program-c-algoritma-kruskal.html
3.
4. #include <cstdlib>
5. #include <iostream>
6. #include <fstream>
7.
8.
9. using namespace std;
10.
11. class kruskal
12. {
13. private:
14. int n ;//no of nodes
15. int noe; //no edges in the graph
16. int graph_edge[100][4];
17.
18. int tree[10][10];
19.
20. int sets[100][10];
21. int top[100];
22.
23. public:
24. int read_graph();
25. void initialize_span_t();
26. void sort_edges();
27. void algorithm();
28. int find_node(int );
29. void print_min_span_t();
30. };
31.
32. int kruskal::read_graph()
33. {
34. cout << "----------------------------------------------------------------" <<endl;
35. cout << " KELOMPOK 4 " <<endl;
36. cout << " PROGRAM ALGORITMA KRUSKAL ALFAMART DI KABUPATEN TANAH LAUT " <<endl;
37. cout << "----------------------------------------------------------------" <<endl;
38. cout<<endl;
39. cout << " Banyak titik graph : "; cin >> n;
40. noe=0;
41.
42. cout<<"\n Jarak antar tiap titik:\n";
43.
44. for(int i=1;i<=n;i++)
45. {
46. for(int j=i+1;j<=n;j++)
47. {
48. cout << " ("<<i<<" , "<<j<<") = ";
49. float w;
50. cin>>w;
51. if(w!=0)
52. {
53. noe++;
54.
55. graph_edge[noe][1]=i;
56. graph_edge[noe][2]=j;
57. graph_edge[noe][3]=w;
58. }
59. }
60. }
61. }
62.
63. void kruskal::sort_edges()
64. {
65. /** Sort the edges using bubble sort in increasing order******/
66.
67. for(int i=1;i<=noe-1;i++)
68. {
69. for(int j=1;j<=noe-i;j++)
70. {
71. if(graph_edge[j][3]>graph_edge[j+1][3])
72. {
73. int t=graph_edge[j][1];
74. graph_edge[j][1]=graph_edge[j+1][1];
75. graph_edge[j+1][1]=t;
76.
77. t=graph_edge[j][2];
78. graph_edge[j][2]=graph_edge[j+1][2];
79. graph_edge[j+1][2]=t;
80.
81. t=graph_edge[j][3];
82. graph_edge[j][3]=graph_edge[j+1][3];
83. graph_edge[j+1][3]=t;
84. }
85. }
86. }
87.
88. cout<<"\n\n Setelah Jarak diurutkan adalah ::\n";
89.
90. for(int i=1;i<=noe;i++)
91. cout << " (" << graph_edge[i][1] << " , "<<graph_edge[i][2] << " ) = " <<graph_edge[i][3]<<endl;
92. }
93.
94. void kruskal::algorithm()
95. {
96.
97. for(int i=1;i<=n;i++)
98. {
99. sets[i][1]=i;
100. top[i]=1;
101. }
102.
103. cout<<"\n Rentang Yang di Pakai\n\n";
104.
105. for(int i=1;i<=noe;i++)
106. {
107. int p1=find_node(graph_edge[i][1]);
108. int p2=find_node(graph_edge[i][2]);
109.
110. if(p1!=p2)
111. {
112. cout<<"Rentang yg masuk ke pohon ::"
113. <<" < "<<graph_edge[i][1]<<" , "
114. <<graph_edge[i][2]<<" > "<<endl<<endl;
115.
116. tree[graph_edge[i][1]][graph_edge[i][2]]=graph_edge[i][3];
117. tree[graph_edge[i][2]][graph_edge[i][1]]=graph_edge[i][3];
118.
119. // Mix the two sets
120.
121. for(int j=1;j<=top[p2];j++)
122. {
123. top[p1]++;
124. sets[p1][top[p1]]=sets[p2][j];
125. }
126.
127. top[p2]=0;
128. }
129. else
130. {
131. cout<<"Jika "
132. <<" < "<<graph_edge[i][1]<<" , "
133. <<graph_edge[i][2]<<" > "<<"di masukkan, maka terbentuk siklus. jadi di hapus\n\n";
134. }
135. }
136. }
137.
138. int kruskal::find_node(int n)
139. {
140. for(int i=1;i<=noe;i++)
141. {
142. for(int j=1;j<=top[i];j++)
143. {
144. if(n==sets[i][j])
145. return i;
146. }
147. }
148.
149. return -1;
150. }
151.
152.
153. int main(int argc, char *argv[])
154. {
155. kruskal obj;
156. obj.read_graph();
157. obj.sort_edges();
158. obj.algorithm();
159.
160. system("PAUSE");
161. return EXIT_SUCCESS;
162. }
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 step 3.
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 :
#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 :
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.
0 Komentar