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
|
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
|
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.
Tidak ada komentar:
Posting Komentar