Kali
ini saya akan menjelaskan tentang Graf (Djikstra)
dan Pohon (Kruskal)
Djikstra
A.
Pengertian
Djikstra
Algoritma
Djikstra, penemunya adalah seorang ilmuwan komputer, Edsger Djikstra, adalah
sebuah algoritma yang dipakai dalam memecahkan permasalahan jarak terpendek
untuk sebuah graph berarah dengan bobot-bobot sisi yang bernilai positif.
B. Tujuan
Algoritma Djikstra
1. Tujuan
Algoritma Djikstra 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.
C. Urutan
Logika Algoritma Djikstra
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.
Kruskal
A.
Pengertian
Kruskal
Algoritma kruskal adalah sebuah algoritma dalam teori graf yang mencari
sebuah minimum spanning tree untuk sebuah graf berbobot yang terhubung. Ini
berarti menemukan subset dari tepi yang membentuk sebuah pohon yang mencakup
setiap titik , di mana berat total dari semua tepi di atas pohon diminimalkan..
Jika grafik tidak terhubung, maka menemukan hutan rentang minimum (pohon
rentang minimum untuk setiap komponen terhubung).
Algoritma Kruskal juga tergolong
algoritma Greedy dalam teori graf yang digunakan untuk mencari minimum spanning
tree. Algoritma ini pertama kali muncul pada tahun 1956 dalam sebuah tulisan
yang ditulis oleh Joseph Kruskal.
Algoritma Kruskal adalah contoh dari algoritma rakus. Algoritma ini pertama
kali muncul dalam Prosiding American Mathematical Society, hal 1956.
Dasar
pembentukan algoritma Kruskal berasal dari analogi growing forest. Growing
forest maksudnya adalah untuk membentuk pohon merentang minimum T dari graf
G adalah dengan cara mengambil satu per satu sisi dari graf G dan memasukkannya
ke dalam pohon yang telah terbentuk sebelumnya. Seiring dengan berjalannya
iterasi untuk setiap sisi, maka forest akan memiliki pohon yang semakin
sedikit. Oleh sebab itu, maka analogi ini disebut dengan growing forest.
Algoritma Kruskal akan terus menambahkan sisi – sisi ke dalam hutan yang sesuai
hingga akhirnya tidak akan ada lagi forest dengan, melainkan hanyalah sebuah
pohon yang merentang minimum.
Graph:
kumpulan dua himpunan yaitu himpunan titik (vertex / simpul / node) dan
kumpulan dari garis (edge).
Tree:
graph tak berarah yang terhubung dan tidak mengandung sirkuit.
Sirkuit: simpul awal = simpul akhir.
Secara umum Algoritma
Kruskal ditulis :
1. T
masih kosong .
2. pilih
sisi (i,j) dengan bobot minimum.
3. pilih
sisi (i,j) dengan bobot minimum berikutnya yang tidak membentuk cycle di T, tambahkan (i,j) ke T.
4. Ulangi
langkah 3 sebanyak (n-2) kali.
5. Total
langkah (n-1) kali
B. Karakteristik
Algoritma Kruskal Sifat Algoritma Kruskal ini:
1. Ia
bekerja tidak hanya dengan grafik diarahkan.
2. Ia
bekerja dengan bobot dan tidak grafik tertimbang. Tapi, yang lebih menarik,
apabila tepi yang berbobot.
3. Kruskal
adalah jenis algoritma serakah yang menghasilkan solusi optimal MST.
C. Kelebihan
dan Kekurangan Algoritma Kruskal
Terdapat dua macam algoritma tipe
greedy yang dapat memenuhi pemecahan masalah pohon merentang ini. Yaitu
algoritma Prim dan algoritma kruskal, berikut adalah kelebihan dan kekurangan
algoritma Kruskal dibanding algoritma prim.
a. Kelebihan
Algoritma Kruskal Kelebihan algoritma
Kruskal dibanding algoritma prim adalah sebagai berikut :
Sangat cocok
diterapkan saat graf memiliki sisi berjumlah sedikit namun memiliki sangat
banyak simpul, karena orientasi kerja algoritma ini adalah berdasarkan pada
urutan bobot sisi, tidak berdasarkan simpul
b. Kekurangan
Algoritma Kruskal
Beberapa hal yang
menjadi kekurangan algoritma kruskal dibanding algoritma prim:
Kurang cocok
digunakan saat graf lengkap atau yang mendekati lengkap, dimana setiap simpul
terhubungkan dengan semua simpul yang lain. Karena algoritma Kruskal menitik
beratkan pada pencarian sisi, dimana sisi-sisi tersebut harus diurutkan dan ini
memakan waktu yang tidak sedikit.
Listing Djikstra (graf)
Listing Kruskal (pohon)
Hasil Running Djikstra
Hasil Running Kruskal
Sumber :
