makalah algoritma kruskal

Universitas Sains Al-Quran Wonosobo Perancangan & Analisis 1

BAB I

PENDAHULUAN

A. Latar Belakang

Di zaman yang serba modern ini, dunia ilmu teknologi berkembang sangat pesat,

dan hampir merata ditanah air dari kota sampai pelosok pun terjamah teknologi.

Sehingga sebagai pelaku utama yang berkecimpung dalam dunia teknik maupun

(IT) seharusnya sudah mampu untuk bersaing tidak hanya dalam lingkup global

tapi ranah yang lebih luas, bahkan dapat mengembangkan sebuah projek sendiri.

Mengingat sekarang dunia teknologi berkembang dimana-mana khususnya

dikawasan asia, bersaing membuat suatu program atau projek-projek yang

notabene teknologinya sangat canggih bahkan disingkronkan dengan

mikrokontroller dan mikroprosesor. Maka dari itu, dalam rangka mensejajarkan

teknologi dengan negara asia yang lain dan sumber daya yang ada, sebagai anak

komputer (IT) dituntut agar belajar dengan semaksimal mungkin secara efisien

dan efektif dalam segala hal terutama dalam mendalami sebuah algoritma yang

menjadi dasar landasan untuk mengembangkan suatu program atau aplikasi. Dan

tentunya disuatu saat akan bermanfaat. Selain itu, juga mampu bersaing

dikawasan Asean ini. Yang tentunya sangat ketat dari segi keunggulan maupun

kelemahan dari masing-masing negara yang bersangkutan dengan

perkembangan teknologi masa depan.

Adapun dalam makalah ini penulis akan membahas salah satu metode

penyelesaian kasus menggunakan algoritma kruskal dari tujuh metode yang

telah ditentukan yang notabene merupakan metode yang berguna untuk

menyelesaikan dan memahami suatu masalah yang bersangkutan dengan

spanning tree, dengan harapan suatu masalah dapat diselesaiakan dengan lebih

efisien dengan menggunakan algoritma tersebut.

B. Rumusan Masalah

Berdasarkan latar belakang, maka masalah yang muncul berdasarkan

uraian di atas dirumuskan sebagai berikut:

1. Apakah definisi dari algoritma kruskal ?

2. Bagaimana karakteristik algoritma kruskal ?

3. Apakah kelebihan dan kekurangan algoritma kruskal?

4. Contoh algoritma kruskal?


C. Tujuan

Berdasarkan rumusan masalah, maka apabila tujuan tercapai adalah

sebagai berikut:

1. Agar mahasiswa mengetahui lebih mendalam tentang pengertian algoritma

kruskal

2. Agar mahasiswa mampu mengimplementasiakan atau menerapakan

penyelesaian minimum spanning dengan Algoritma kruskal ataupun metode

lain yang terkait.

3. Mempelajari bagaimana menganalisa suatu perancangan algoritma yang

sudah berjalan dan tentunya masih mempunyai kekurangan dari sisi lain yang

tidak terlihat.

D. Manfaat

Manfaat adanya penyususnan makalah perancangan dan analisis

algoritma ini yang diharapkan apabila tujuan terpenuhi adalah membantu

mahasiswa untuk bisa menerapkan ataupun mengimplementasikanya dalam

kehidupan sehari-hari. Bahkan bisa mengimplementasiakan matakuliah

perancangan dan analisis algoritma dengan minimum spanning (MST)

khususnya adalah algoritma kruskal. Selain itu, mampu menganalisa suatu

perancangan yang sulit jadi lebih mudah untuk banyak pengguna atau user.


BAB II

PEMBAHASAN

A. Pengertian 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 (vertek/simpul/node) dan

kumpulan dari garis (edge).

Tree: graph tak berara yang terhubung dan tidak mengandung sirkuit. Sirkuit:

simpil 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 Alogritma kruskal

a. Sifat algoritma kruskal ini:

1. Bekerja tidak hanya dengan grafik diarahkan.

2. Bekerja dengan bobot dan tidak grafik tertimbang. Tapi, yang lebih

menerik, apabila tepi yang berbobot.

3. Kruskal adalah jenis algoritma yang menghasilkan solusi optimal

MST

b. Langkah Algoritma Kruskal

Langkah-langkah utama Algoritma Kruskal adalah sebagai berikut:

1. Atur tepi berat: paling berat pertama dan terberat terakhir.

2. Pilih yang 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 digunakan 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:

Kuranag 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 Masalah dengan Algoritma Kruskal

Contoh penyelesaian kasus minimum spanning tree dengan algoritma kruskal,

diketahui sebuah pohon graf berbobot seperti gambar berikut 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 simpul-simpul

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.

B. Ruas D,F A. Ruas A,B D,F

C. Ruas E,G D. Ruas A,D C,E

F. Ruas C,E E. Ruas B,C B,E F,G


Selesai MST Graf G dengan 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

H. Ruas B,D E,F D,E G. Ruas DB dihapus

J. Ruas E,F dihapus I. Ruas D,E dihapus

K. 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 (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 yang tekecil 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)).

f. Ruas selanjutnya dengan bobot yang terkecil saat ini yaitu ruas BC, BE

dan FG dengan bobot 8. Pilih acak ruas BC dan hapus ruas BE (gambar

2.11) dan ruas FG karena akan membentuk sirkuit jika dihubungkan

(gambar 2.11(f)).

g. Untuk ruas-ruas selanjutnya, BD, EF, dan DE dihapus karena akan

membentuk sirkuit jika dihubungkan gambar 2.11(h), gambar 2.11(i),

gambar 2.11(j)).

h. Gambar 2.11 (k) adalah Minimum spanning Tree yang dihasilkan.


BAB III

KESIMPULAN DAN SARAN

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.

Sedangkan untuk Algoritma Kruskal lebih menitik beratkan pada pemilihan sisi

berdasarkan urutan bobotnya. Untuk itu terlebih dahulu harus mengurutkan sisi

berdasarkan pada bobotnya, dan algoritma ini lebih cocok untuk pohon dengan

jumlah simpul sedikit kurang disarankan untuk pohon dengan jumlah simpul

yang banyak.

B. Saran

Setelah selesainya pembuatan makalah dari makul Perancangan dan Analisis

Algoritma terlaksana, adapun saran-saran penulis sampaikan dalam proses

pengerjaan terutama pada bagian menganalisa program, pembahasan masalah

diantarannya sebagai berikut:

1. Untuk pembuatan makalah atau laporan kedepanya, saya mengharapkan

adanya kritik dan saran yang sifatnya membangun dari semua pihak

dosen maupun seluruh mahasiswa yang sempat membaca makalah makul

Perancangan dan Analisis Algoritma yang berjudul Penyelesaian

Minimum SpanningTree dengan Algoritma Kruskal.

2. Agar kedepanya dosen pendamping dalam teori Perancangan dan


Analisis Algoritma untuk lebih mempertimbangkan adanya penjelesan

(pembekalan) tentang materi terlebih dahulu ketimbang langsung

membuat laporan tanpa suatu adanya penjelasan. Menurut penulis sendiri

materi tanpa penjelasan itu lebih grambyang secara istilah.

3. Agar kedepanya untuk pembuatan projek ataupun laporan untuk

kedepanya, penulis sangat mengharapkan adanya penjelasan materi atau

teori terlebih dahulu. Disamping itu, karena untuk membuat laporan

tanpa adanya penjelasan tentang teori terkait itu, akan mempersulit

mahasiswa dalam mengerjakan tugas yang telah diberikan. Bahkan

malah menjadi beban terutama untuk penulis sendiri.


DAFTAR PUSTAKA

http://bobo-magazine.blogspot.co.id/2010/05/algoritma-kruskall.html

http://slidegur.com/doc/1714614/minimum-spanning-tree

http://repository.amikom.ac.id/files/Publikasi_07.11.1385.pdf

http://allaboutalgoritma.blogspot.co.id/2011/04/pemodelan-sistem-

minumun-spanning-tree.html

http://wahyumiftahulhuda.blogspot.co.id/2014/05/pengertian-algoritma-

prim-dan-program-c.html

http://www.tutorvista.com/content/math/kruskals-algorithm/

http://repository.unib.ac.id/9217/2/I,II,III,II-14-ris-FT.pdf

makalah algoritma kruskal

Technology