PERBANDINGAN ALGORITMA PRIM DAN KRUSKAL UNTUK MENYELESAIKAN MASALAH MINIMUM SPANNING TREE
NASKAH PUBLIKASI
diajukan oleh: Yuni Ardita Sari Dewi 07.11.1385
kepada JURUSAN TEKNIK INFORMATIKA SEKOLAH TINGGI MANAJEMEN INFORMATIKA DAN KOMPUTER AMIKOM YOGYAKARTA YOGYAKARTA 2014 1
2
COMPARISON OF PRIM AND KRUSKAL ALGORITHM TO SOLVE MINIMUM SPANNING TREE PROBLEM PERBANDINGAN ALGORITMA PRIM DAN KRUSKAL UNTUK MENYELESAIKAN MASALAH MINIMUM SPANNING TREE
Yuni Ardita Sari Dewi Andi Sunyoto Jurusan Teknik Informatika STMIK AMIKOM YOGYAKARTA
ABSTRACT Graph theory has been developed and widely applied to everyday life until now. One of graph theory concepts that developed in this age is tree concept. Tree concept is being the most important and popular concept because it is able to support concept of problem solving in a variety of applied graphs. Applications that uses concept of trees such as construction of roads and railroad, computer networking, finding path to solve travelling salesman problem, etc. Presenting a graph with tree concepts for solving problems like building graph to be a Minimum Spanning Tree (MST). Algorithm Prim and Kruskal algorithm are the most common algorithms used to solve minimum spanning tree problem. In general, both algorithms will provide a same output. But in fact each algorithm has its advantages and disadvantages respectively. Advantages and disadvantages of this algorithm allows the user to choose which one is more effective to solve MST problem.
Keywords: graph, tree, minimum spanning tree, Kruskal, Prim
3
1. PENDAHULUAN Graf merupakan ilmu yang sangat penting dan mampu menyelesaikan banyak permasalahan. Aplikasi graf dan pohon banyak diterapkan pada pemodelan masalah dalam kehidupan sehari hari. Salah satu bahasan yang cukup penting dalam teori graf dan pohon adalah pohon merentang minimum (Minimum Spanning Tree / MST). Banyak sekali masalah yang dapat diselesaikan dengan memodelkan masalah tersebut ke dalam graf kemudian diselesaikan dengan menentukan pohon merentang minimum, seperti pada contoh kasus penentuan panjang kabel optimum untuk merancang jaringan listrik di suatu area. Contoh lain misalnya, untuk menentukan rute terpendek untuk menjelajahi kota kota sehingga sejumlah titik tertentu di kota tersebut tepat dilewati satu kali. Ada beberapa cara yang lazim digunakan dalam memecahkan masalah pohon merentang minimum ini. Algoritma prim dan algoritma kruskal merupakan dua cara yang paling umum digunakan untuk membentuk pohon merentang minimum. Kedua algoritma ini terbukti mampu menghasilkan pohon merentang minimum. Namun dalam praktiknya, pengguna seringkali merasa sulit untuk memilih algoritma mana yang lebih baik dan lebih efektif untuk diterapkan pada graf jenis tertentu. 2. LANDASAN TEORI 2.1. Graf Graf merupakan bahasan yang sudah tua usianya namun memiliki banyak terapan sampai saat ini. Graf digunakan untuk merepresentasikan objek-objek diskrit dan hubungan antara objek-objek tersebut. Representasi visual dari graf adalah dengan menyatakan objek sebagai noktah, bulatan atau titik. Sedangkan hubungan antar objek dinyatakan dengan garis.1 2.1.1.
Teori Graf Graf (Graph) didefinisikan sebagai :
G = {V, E} Keterangan : V (G) (vertex/ simpul) : himpunan tidak kosong dari simpul-simpul (vertex/ node) digambarkan dalam titik – titik. E (G) (edge/ sisi) : himpunan sisi – sisi yang digambarkan dalam garis – garis yang menghubungkan sepasang simpul. Dapat dikatakan graf adalah kumpulan simpul – simpul yang dihubungkan oleh sisi – sisi.
1
Rinaldi Munir, Matematika Diskrit Revisi Kelima, (Bandung : Informatika, 2012), hal 353
4
Gambar 2. 1 Graf G1
Pada G1 diatas, graf terdiri dari himpunan V dan E yaitu: V = {A, B, C, D} E = {e1, e2, e3, e4} ; bisa kita tulis = {(A,B),(B,C),(B,C),(A,C)} Aplikasi graf sangat luas. Graf dipakai dalam berbagai disiplin ilmu maupun dalam kehidupan sehari-hari. Penggunaan graf di berbagai bidang tersebut adalah untuk memodelkan persoalan. Beberapa terminologi dasar yang harus diketahui: 2.1.2.
Graf Berarah (Directed Graph/Digraph) 2
Graf berarah adalah graf yang setiap sisinya diberi orientasi arah. Dalam hal ini sisi yang ditulis (v1,v2) berbeda dengan sisi (v2, v1).
Gambar 2. 2 Graf Berarah
2.1.3.
Graf berbobot / berlabel (Weight Graf) Graf berbobot adalah graf yang setiap sisinya diberi sebuah harga.
3
Dalam
aplikasinya, bobot suatu garis lebih tepat dibaca sebagai : ”jarak”, “biaya”, ”panjang”
2 3
Ibid, hal 358 Ibid, hal 376
5
,”kapasitas”, dan lain sebagainya. Label suatu garis dapat diberikan pada graf berarah maupun tidak berarah.
Gambar 2. 3 Graf Berbobot
2.1.4.
Graf Lengkap (Complete Graph) Graf lengkap adalah graf sederhana, tidak mengandung gelang (sisi yang kedua
simpulnya sama) maupun sisi ganda (dua sisi yang memiliki simpul asal dan simpul tujuan yang sama), serta setiap sisinya mempunyai sisi ke simpul lain.
2.1.5.
4
Bertetangga (Adjacent) Dua buah simpul pada graf tak berarah ikatan bertetangga bila keduanya 5
terhubung dengan sebuah sisi. Dapat dikatakan jika ada v1 dan v2 yang bertetangga, maka harus ada sisi (v1 ,v2) 2.1.6.
Bersisian (Incident) Untuk sembarang sisi e = (v1,v2), sisi e dikatakan bersisian dengan simpul v1 6
dan simpul v2. 2.1.7.
Simpul terpencil (Isolated Vertex) Simpul terpencil adalah simpul yang tidak mempunyai sisi yang bersisian
dengannya. Dengan kata lain simpul ini ialah simpul yang tidak satupun bertetangga 7
dengan simpul lain.
4
Ibid, hal 377 Ibid, hal 365 6 Ibid 7 Ibid 5
6
2.1.8.
Lintasan (Path) Lintasan yang panjangnya n dari simpul awal v0 ke simpul akhir vn di dalam graf
G ialah barisan berselang – seling simpul – simpul dan sisi-sisi yang berbentuk v0, e1, v1, e2 ,….., vn-1,en, vn sedemikian sehingga e1 = (v0, v1), e2 = (v1, v2 ) …, n = (vn-1,vn 8
) adalah sisi – sisi dari graf G. 2.1.9.
Sirkuit (Circuit) atau siklus Siklus adalah lintasan yang berawal dan berakhir pada simpul yang sama.9
2.1.10. Terhubung (Connected) Graf disebut graf terhubung jika untuk setiap pasang simpul v1 dan v2 di dalam himpunan V terdapat lintasan dari v1 ke v2, yang juga berarti ada lintasan dari v2 ke v1 (untuk graf berarah).10 2.2.
Pohon Rentang Minimum Jika G adalah graf berbobot, maka bobot dari pohon rentang T dari G
didefinisikan sebagai jumlah bobot pada semua sisi di T. Pohon rentang yang berbeda memiliki bobot yang berbeda pula. Di antara pohon rentang di G, pohon yang memiliki bobot paling minimum dinamakan Pohon Rentang Minimum11. Pohon ini merupakan pohon rentang yang paling penting. Pohon rentang minimum memiliki terapan yang sangat luas dalam dunia nyata. Misalnya, pembangunan rel kereta api yang menghubungkan
sejumlah
kota.
Pembangunan
jalur
kereta
ini
tidak
perlu
menghubungkan langsung dua buah kota; tetapi cukup membangun jalur kereta seperti pohon rentang. Karena di dalam graf mungkin terdapat beberapa pohon rentang, maka harus dicari pohon rentang minimum.Terdapat dua buah algoritma untuk membangun pohon rentang minimum. Yaitu algoritma Prim dan algoritma Kruskal. 2.3.
Algoritma Prim Konsep dasar yang digunakan dalam algoritma Prim adalah pada setiap langkah,
pilih sisi dari graf G yang berbobot minimum yang terhubung dengan pohon merentang T yang telah terbentuk, dan tidak membentuk sirkuit.12 Langkah-langkah algoritma Prim13 :
8
Rinaldi Munir, Matematika Diskrit Revisi Kelima, (Bandung : Informatika, 2012), hal 369 Ibid, hal 370 10 Ibid, hal 371 11 Ibid, hal 450 12 Ibid, hal 451 13 Ibid 9
7
1.
Ambil sisi dari graf G yang berbobot minimum, masukkan ke dalam T.
2.
Pilih sisi (u,v) yang mempunyai bobot minimum dan bersisian dengan T, tetapi (u,v) tidak membentuk sirkuit di T. Tambahkan (u,v) ke dalam T.
3.
Ulangi langkah 2 sampai pohon merentang minimum terbentuk, yaitu setelah mengalami pengulangan sebanyak n-2 kali (n adalah jumlah simpul graf G).
start
input G = (V, E) V = simpul E (p,q) = sisi dengan bobot
Cari sisi (p,q) dari E yang berbobot terkecil T<-- {(p,q)}
tidak for i 1 to n-2 do ya Pilih sisi (u,v) dari E yang bobotnya terkecil namun bersisian dengan suatu simpul di dalam T T <--T {(u,v)}
output T = ( V,E ) V = simpul E (u,v) = sisi dengan bobot terkecil
end
Gambar 2. 4 Flowchart Algoritma Prim
2.4.
Algoritma Kruskal Konsep dasar yang digunakan dalam algoritma Kruskal adalah pada setiap
langkah, pilih sisi dari graf G yang berbobot minimum, tetapi sisi tersebut tidak membentuk sirkuit. 14 15
Langkah-langkah algoritma Kruskal
14 15
:
Rinaldi Munir, Matematika Diskrit Revisi Kelima, (Bandung: Informatika, 2012), hal 454 Ibid, hal 455
8
1. Lakukan pengurutan terhadap setiap sisi di graf G mulai dari sisi dengan bobot terkecil. 2. Pilih sisi (u,v) yang mempunyai bobot minimum yang tidak mempunyai sirkuit di T. Tambahkan (u,v) ke dalam T. 3. Ulangi langkah 2 sampai pohon merentang minimum terbentuk, yaitu ketika sisi di dalam pohon merentang T berjumlah n-1 (n adalah jumlah simpul graf G).
Gambar 2. 5 Flowchat Algoritma Kruskal
3. ANALISIS DAN PERANCANGAN 3.1.
Analisis Sistem Perancangan Analisis Sistem adalah penguraian dari suatu sistem informasi
secara utuh ke dalam bagian – bagian komponennya dengan maksud untuk
9
mengidentifikasikan dan mengevaluasi permasalahan, kesempatan, hambatan yang terjadi dan kebutuhan yang diharapkan sehingga dapat diusulkan perbaikan.16 3.1.1.
Analisis SWOT Analisis yang digunakan penulis dalam hal ini adalah metode SWOT (Strength,
Weakness, Opportunities, Threats), yaitu dengan menganalisa kekuatan, kelemahan, peluang, serta ancaman dari aplikasi minimum spanning tree prim dan kruskal ini. 3.1.1.1. Kekuatan (Strength) Aplikasi ini memudahkan untuk menentukan bobot minimum suatu pohon merentang secara efektif berdasarkan kasus tertentu dengan algoritma prim dan kruskal. Inteface yang menarik dan mudah digunakan. 3.1.1.2. Kelemahan (Weakness) Aplikasi ini hanya dapat menghitung input node dan sisi secara terbatas. 3.1.1.3. Peluang (Opportunity) Memberikan kemudahan dalam menyelesaikan masalah minimum spanning tree secara lebih efektif dibandingkan dengan cara manual. Fitur dan teknologi kemampuan software yang berkembang mendukung hasil yang semakin baik. 3.1.1.4. Ancaman (Threat) Ancaman utama dalam pengembangan aplikasi ini adalah adanya aplikasi yang sejenis dengan fitur yang lebih baik dan lengkap. 3.1.2.
Analisis Kebutuhan
3.1.2.1. Analisis Kebutuhan Fungsional Analisis Kebutuhan Fungsional merupakan layanan yang harus disediakan untuk membangun sistem. a.
Sistem dapat menampilkan Form Utama sebagai tempat user untuk memulai menggunakan aplikasi minimum spanning tree.
b.
Sistem dapat memuat file .txt untuk diproses lebih lanjut
c.
Sistem mampu menyimpan file .txt hasil dari spanning tree yang telah terbentuk
d.
Sistem mampu memberikan 2 penyelesaian minimum spanning tree dengan algoritma prim maupun kruskal
e.
Sistem mampu menampilkan bentuk spanning tree dari data yang telah di – load user
16
Hartono, Jogiyanto. Analisis dan Desain Sistem Informasi Pendekatan Terstruktur Teori dan Praktek Aplikasi Bisnis, (Yogyakarta: Andi, 1999), hal : 129
10
f.
Sistem mampu menghapus data – data spanning tree yang telah terbentuk
g.
Keluar dari aplikasi Minimum Spanning Tree
h.
Bantuan untuk user tentang penggunaan aplikasi Minimum Spanning Tree
3.1.2.2. Analisis Kebutuhan Non-Fungsional Analisis Kebutuhan Non - Fungsional merupakan penjelasan analisis yang mencakup spesifikasi hardware atau alat yang akan digunakan serta minimal alat yang akan digunakan untuk pembuatan dan menjalankan aplikasi. 1. Kebutuhan Perangkat Keras (Hardware) a. Spesifikasi Perangkat Keras Yang Digunakan Untuk Pembuatan Aplikasi Tabel 3. 1 Kebutuhan Perangkat Keras Untuk Pembuatan Aplikasi Perangkat Keras
Spesifikasi
Prosesor
Intel® Core ™ Duo 2.80 GHz
Motherboard
Release Version
Memory
2 GB
Hardisk
Samsung 160 GB
Optical Drive
DVD RW “Lite On”
Keyboard + mouse
Okaya
Speaker
Simbadda
Printer
Canon IP 1800
Monitor
Samsung “17” inci
b. Spesifikasi Minimal Perangkat Keras Yang Dibutuhkan Untuk Menjalankan Aplikasi Tabel 3. 2 Kebutuhan Minimal Perangkat Keras Untuk Menjalankan Aplikasi Perangkat Keras
Spesifikasi
Prosesor
500 Mhz Ultra 60, Sun Blade 150 or equivalent workstation
Memory
512 Megabytes
Disk Space
150 Megabytes or free disk space
2. Kebutuhan Perangkat Lunak (Software) a. Spesifikasi Perangkat Lunak Yang Digunakan Untuk Pembuatan Aplikasi
11
a. Sistem Operasi Windows XP SP2 b. Jdk-6u11-windows-i586-p c.
Netbeans-7.0-ml-windows
d. UML 6 b. Spesifikasi Perangkat Lunak Yang Digunakan Untuk Menjalankan Aplikasi a. Sistem Operasi Windows XP SP2 b. Java Runtime Environment (JRE) versi 5 3.1.3.
Analisis Kelayakan Sistem
3.1.3.1. Analisis Kelayakan Segi Teknik Analisis dari perbandingan algoritma prim dan kruskal akan menghasilkan aplikasi minimum spanning tree untuk mempermudah menentukan bobot minimum dari sebuah pohon merentang. Aplikasi ini
merupakan aplikasi berbasis java yang akan
dibangun dan dibuat dengan benar mengikuti permasalahan yang ada. Untuk mencapai tujuan maka dari itu dibutuhkan masalah apa saja yang timbul dan dapat diselesaikan oleh aplikasi ini. 3.1.3.2. Analisis Kelayakan Segi Hukum Analisis kelayakan dari segi hukum, menampilkan apakah aplikasi tidak melanggar hukum dan norma masyarakat luas. Aplikasi minimum spanning tree merupakan aplikasi berbasis java yang bertujuan untuk menentukan algoritma yang efektif dalam menyelesaikan masalah minimum spanning tree. Dari segi hukum negara, aplikasi ini tidak melanggar serta tidak mengandung hal-hal yang menyinggung masalah SARA dan pornografi. 3.1.3.3. Analisis Kelayakan Segi Operasional Sistem
yang
dibangun
dapat
memenuhi
tujuan
pengguna
dalam
menentukan algoritma yang efektif pada suatu kasus minimum spanning tree. Hal ini lebih optimal dibandingkan dengan perhitungan secara manual. 4. IMPLEMENTASI DAN PEMBAHASAN Berikut terdapat 2 buah graf yang digunakan untuk menentukan algoritma manakah yang lebih efektif di antara algoritma prim dan kruskal dalam menyelesaikan masalah minimum spanning tree.
12
Gambar 4. 1 Graf Uji Kasus
4.1. Uji Kasus I: Tabel 4. 1 Soal Uji Kasus I
start vertex
end vertex
weight edge
1
4
5
1
2
7
2
3
8
2
5
7
3
5
5
4
6
6
4
2
9
4
5
15
5
6
8
5
7
9
6
7
11
Apabila dinyatakan dengan graf adalah sebagai berikut :
Gambar 4. 2 Graf Uji Kasus I
13
Berikut adalah penyelesaian minimum spanning tree untuk graf uji kasus I dengan algoritma Prim dan Kruskal secara manual. Tabel 4. 2 Penyelesaian dengan Algoritma Prim dan Kruskal Secara Manual
Algoritma Prim
Algoritma Kruskal
Langkah Terpilih (Simpul) 0 1 2 3
1 4 6 2
4
5
5
3
6
7
Sisi Terbentuk {(1,4)} {(1,4),(4,6)} {(1,4),(4,6), (1,2)} {(1,4),(4,6),(1,2), (2,5)} {(1,4),(4,6),(1,2), (2,5),(5,3)} {(1,4),(4,6),(1,2), (2,5),(5,3), (5,7)}
Terpilih (Sisi)
Simpul Masuk
(1,4) (3,5) (4,6) (1,2)
{1,4} {1,3,4,5} {1,3,4,5,6} {1,2,3,4,5,6}
(2,5)
{1,2,3,4,5,6}
(2,3)
Ditolak
(5,7)
{1,2,3,4,5,6,7}
Bobot total w (e) = 5 + 6 + 7 + 7 + 5+ 9 = 39 Pohon merentang minimum yang terbentuk adalah
Gambar 4. 3 Pohon Merentang Minimum Graf Uji Kasus I
Apabila dihitung dengan menggunakan aplikasi program MST Prim dan Kruskal hasil bobot yang didapat antara kedua algoritma tersebut adalah sama yaitu 39.
14
Gambar 4. 4 Hasil Perhitungan dengan Aplikasi MST Prim dan Kruskal
4.2. Uji Kasus II: Tabel 4. 3 Soal Uji Kasus II
start vertex 1 1 1 1 2 2 2 3 3 4
end vertex 2 3 4 5 3 4 5 4 5 5
Apabila dinyatakan dengan graf adalah sebagai berikut :
15
weight edge 4 13 5 12 15 37 13 5 20 2
Gambar 4. 5 Graf Uji Kasus II
Berikut adalah penyelesaian minimum spanning tree untuk graf uji kasus II dengan algoritma Prim dan Kruskal secara manual. Tabel 4. 4 Penyelesaian dengan Algoritma Prim dan Kruskal Secara Manual
Algoritma Prim
Algoritma Kruskal
Langkah Terpilih (Simpul) 0 1 2 3
4 5 1 2
4
3
Sisi Terbentuk {(4,5)} {(4,5),(1,4)} {(4,5),(1,4), (1,2)} {(4,5),(1,4), (1,2), (3,4)}
Bobot total w (e) = 2+5+5+4 =16 Pohon merentang minimum yang terbentuk adalah
16
Terpilih (Sisi) (4,5) (1,2) (1,4) (3,4)
Simpul Masuk {4,5} {1,2,4,5} {1,2,4,5} {1,2,3,4,5}
Gambar 4. 6 Pohon Merentang Minimum Graf Uji Kasus II
Apabila dihitung dengan menggunakan aplikasi program MST Prim dan Kruskal hasil bobot yang didapat antara kedua algoritma tersebut adalah sama yaitu 16.
Gambar 4. 7 Hasil Perhitungan dengan Aplikasi MST Prim dan Kruskal
17
5. PENUTUP 5.1. Kesimpulan 1. Algoritma Prim dan algoritma Kruskal dapat menyelesaikan permasalahan pencarian pohon merentang minimum dengan tepat. 2. Algoritma Prim menitikberatkan pada proses pencarian simpul, sedangkan algoritma Kruskal bekerja dengan menitikberatkan pada proses pencarian sisi. 3. Algoritma Prim lebih efektif dibandingkan dengan algoritma Kruskal saat graf yang diberikan memiliki banyak sisi dengan simpul yang sedikit (graf lengkap). 4. Algoritma Kruskal lebih efektif dibandingkan dengan algoritma Prim saat graf yang diberikan memiliki banyak simpul dengan sisi yang sedikit. 5. Aplikasi MST Prim & Kruskal bisa membantu untuk menghitung MST (Minimum Spanning Tree) secara lebih cepat dan efektif dengan membandingkan 2 algoritma yaitu prim dan kruskal dari sebuah graf berlabel/ berbobot (Weight Graf) sederhana secara otomatisasi. 5.2. Saran 1.
Pada aplikasi MST Prim dan Kruskal model input yang digunakan masih menggunakan angka, untuk kedepannya dapat dikembangkan dengan model input berupa graf ataupun huruf misalnya nama kota, daerah, dll.
2. Aplikasi yang penulis rancang fiturnya masih sangat sederhana, sehingga diharapkan nantinya bisa dikembangkan lagi dengan menambah fitur – fitur lainnya, misalnya adanya fitur mencetak hasil penyelesaian pohon merentang minimum dengan algoritma prim dan kruskal ke dalam media kertas. 3. Perhitungan waktu pada aplikasi supaya lebih detail. Untuk perhitungan waktu algoritma prim meliputi detail waktu pencarian sisi awal yang berbobot minimum, sisi yang bersisian tidak membentuk sirkuit, dan proses perulangan langkah hingga terbentuk MST. Untuk perhitungan waktu algoritma kruskal meliputi detail waktu pengurutan sisi, pencarian sisi yang berbobot minimum yang tidak membentuk sirkuit dan proses perulangan hingga terbentuk MST. 4. Penulis menyarankan untuk memperhatikan kekurangan yang ada sehingga akan mudah mencari penyelesaiannya dan membuat aplikasi ini menjadi semakin kompleks.
18
DAFTAR PUSTAKA Munir, Rinaldi. 2012. Matematika Diskrit Revisi Kelima, Informatika, Bandung. Hartono, Jogiyanto. 1999. Analisis dan Desain Sistem Informasi Pendekatan Terstruktur Teori dan Praktek Aplikasi Bisnis, Andi, Yogyakarta.
19
