BAB I
PENDAHULUAN
A. Latar Belakang
Dimasa
sekarang dunia ilmu teknologi berkembang begitu pesat sehingga kita selaku
pemeran dalam dunia tersebut hendaknya dapat bersaing dan membuat suatu program
yang nantinya dapat bermanfaat. Maka dari itu dalam mewujudkan hal tersebut
kita dituntut untuk dapat bekerja secara efisien dan efektif dalam segala hal,
salah satu cara terbaik untuk dapat bekerja efisien adalah dengan menggunakan
sebuah algoritma.
Dalam
makalah ini kami ingin membahas salah satu metode penyelesaian kasus
menggunakan algoritma Kruskal yang merupakan salah satu metode yang berguna
untuk menyelesaikan dan memahami suatu masalah yang berkaitan dengan spanning
tree, dengan harapan penyelesaian suatu
masalah tersebut akan lebih efisien menggunakan algoritma ini.
B. Rumusan Masalah
1. Apa definisi dari algoritma kruskal ?
2. Bagaimana karakteristik algoritma kruskal ?
3. Apa kelebihan dan kekurangan algoritma kruskal
?
4. Contoh dari algortima kruskal ?
BAB II
PEMBAHASAN
A. Definisi Algoritma 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.1
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.
Langkah
Algoritma Kruskal
Langkah-langkah
utama Algoritma Kruskal adalah sebagai berikut:
1.
Atur tepi berat: paling berat pertama dan terberat
terakhir.
2.
Pilih yang paling ringan tidak diperiksa tepi dari
diagram.
3.
Tambahkan tepi memilih ini ke pohon, hanya jika hal itu
tidak akan membuat siklus.
4.
Menghentikan proses kapanpun n - 1 tepi telah ditambahkan
ke pohon.2
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
D. Contoh Penyelesaian dengan Algoritma Kruskal
Contoh penyelesaian kasus minimun
spanning tree dengan algoritma kruskal, diketahui sebuah graf berbobot seperti
gambar 2.10 dibawah ini
Gambar
2.10 Gambaran Awal graf
Tabel
2. 1 Daftar urut nilai Graf dari sisi terbesar sampai terkecil
|
Bobot
|
Ruas
|
|
|
|
15
|
D,E
|
|
|
|
9
|
B,D
|
E,F
|
|
|
8
|
B,C
|
B,E
|
F,G
|
|
7
|
A,D
|
C,E
|
|
|
6
|
A,B
|
E,G
|
|
|
5
|
D,F
|
|
|
Penyelesaian :
1. Mula-mula kita buat sekumpulan
titik G hanya terdiri dari simpulsimpul saja.
2. Urutkan Ruas dari bobot kecil ke
besar (DF, AB, EG, AD, CE, BC, BE, FG, BD, EF, DE), kemudian berdasarkan urutan
tersebut, kita menambahkan ruas dengan mencegah terbentuknya sirkuit.
a. Pilih ruas
terkecil secara acak
|
 .
b. Penambahan ruas AB tambahkan ruas DF ke dalam tree
|
c.
Penambahan ruas EG d. Penambahan ruas AD
e. Penambahan ruas CE
|
f. Penambahan Ruas BC, dan ruas BE dihapus karena membentuk sirkuit.
|
 |
|
 |
g.
Ruas FG dihapus karena h. Ruas DB dihapus karena membentuk
sirkuit. membentuk sirkuit.
|
i.
Ruas
EF dihapus karena membentuk sirkuit.
|
j.
Ruas DE dihapus karena membentuk sirkut.
|
k.
SELESAI.
MST Graf G dengan Nilai Bobot :
38
Gambar
2.11 Teknik penyelesaian Spanning Tree dengan Metode
Kruskal
Pada Gambar 2.12 langkah-langkah
teknik penyelesaian Minimum
Spanning Tree adalah sebagai
berikut :
a. Pilih ruas terkecil dari
keseluruhan graf secara acak. Ruas DF adalah ruas terkecil dengan bobot 5
(gambar 2.11 (a))
b. Setelah ruas 1 didapatkan, ulangi
lagi pemilihan ruas terkecil secara acak dari keseluruhan graf. Ruas AB dan
ruas EG adalah ruas terkecil dengan bobot 6. Pilih acak ruas AB (Gambar
2.11(b))
c. Lanjutkan untuk ruas yang
selanjutnya, Ruas EG adalah ruas terkecil dengan bobot 6 dan tidak membentuk
sirkuit jika dihubungkan. Maka pilih ruas EG (Gambar 2.11(c))
d. Pilih ruas selanjutnya dengan
bobot yg terkecil saat ini, yaitu ruas AD dan ruas CE dengan bobot 7. Pilih
acak ruas AD (Gambar 2.11(d))
e. Lanjutkan untuk ruas CE adalah
ruas terkecil dengan 7 dan tidak membentuk sirkuit jika dihubungkan. Maka pilih
ruas CE (Gambar
2.11(e))
g. Ruas selanjutnya dengan bobot yg
terkecil saat ini yaitu ruas BC, BE dan
FG dengan bobot 8. Pilih acak ruas BC dan hapus ruas BE (Gambar 2.11(f))
dan ruas FG karena akan membentuk sirkuit jika dihubungkan (Gambar 2.11(g))
h. Untuk ruas-ruas selanjutnya, BD,
EF,dan DE dihapus karena akan membentuk sirkut jika dihubungkan (Gambar
2.11(h), Gambar 2.11(i),
Gambar 2.11(j))
i. Gambar 2.11(k) adalah Minimum
Spanning Tree yang dihasilkan.
BAB III
PENUTUP
A. Kesimpulan
Algoritma
Kruskal merupakan turunan dari algoritma greedy yang mengupayakan pengambilan
pilihan optimum pada setiap langkah dengan harapan akan mendapatkan hasil
optimum global pada akhirnya.
Algoritma
Kruskal menitik beratkan pemilihan sisi berdasarkan urutan bobotnya. Dan karena
terlebih dahulu harus mengurutkan sisi berdasarkan bobotnya, algoritma ini
lebih cocok untuk pohon dengan jumlah simpul sedikit kurang disarankan untuk
pohon dengan jumlah simpul yang banyak.
Daftar
Pustaka
makasi sangat membantu
BalasHapus