"TI POLITALA ALPRO2 2B"

GRAF DAN POHON DALAM ALGORITMA PEMROGRAMAN

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 Program Algortima Kruskal

Matriks Kruskal

Baris/Kolom	1	2	3	4	5	6	7	8	9	10
1	0	27000	0	0	0	0	49000	0	0	0
2	27000	0	3600	0	0	0	0	0	0	0
3	0	3600	0	2400	0	0	0	2700	0	0
4	0	0	2400	0	1900	0	0	0	0	0
5	0	0	0	1900	0	2300	0	3900	3900	0
6	0	0	0	0	2300	0	13000	0	6200	0
7	49000	0	0	0	0	13000	0	0	0	51000
8	0	0	2700	0	3900	0	0	0	1300	0
9	0	0	0	0	3900	6900	0	1300	0	32000
10	0	0	0	0	0	0	51000	0	32000	0

   Running Algoritma Kruskal

Contoh Algoritma Djikstra Pada Kasus Pengantaran Barang Dari PT. Sumber Alfaria Trijaya Banjarmasin Ke Alfamart di Kabupaten Tanah Laut

A.           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 Kruskal :

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 Program Algoritma Djikstra

Matriks Algoritma Djikstra

Baris/Kolom	0		1	2	3	4	5	6	7	8	9
0	0		27000	0	0	0	0	49000	0	0	0
1	27000		0	3600	0	0	0	0	0	0	0
2	0		3600	0	2400	0	0	0	2700	0	0
3	0		0	2400	0	1900	0	0	0	0	0
4	0		0	0	1900	0	2300	0	3900	3900	0
5	0		0	0	0	2300	0	13000	0	6200	0
6	49000		0	0	0	0	13000	0	0	0	51000
7		0	0	2700	0	3900	0	0	0	1300	0
8		0	0	0	0	3900	6900	0	1300	0	32000
9		0	0	0	0	0	0	51000	0	3000	0

Running Algoritma Djikstra

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.