simulasi minimum spanning tree - repository.usd.ac.id · 3. algoritma dan flowchart a. ... bab ini...
TRANSCRIPT
SIMULASI MINIMUM SPANNING TREE
MENGGUNAKAN ALGORITMA KRUSKAL
Skripsi
Diajukan untuk Memenuhi Salah Satu Syarat
Memperoleh Gelar Sarjana Sains
Program Studi Ilmu Komputer
Oleh :
Rina Pertiwi Suherman
NIM : 033124043
PROGRAM STUDI ILMU KOMPUTER JURUSAN MATEMATIKA
FAKULTAS SAINS DAN TEKNOLOGI
UNIVERSITAS SANATA DHARMA
YOGYAKARTA
2008
THE SIMULATION OF MINIMUM SPANNING TREE
USING KRUSKAL ALGORITHM
A Final Thesis
Presented as Partial Fulfillment of The Requirements
for the Degree of Sarjana Sains
in Computer Science
By :
Rina Pertiwi Suherman
Student Number : 033124043
COMPUTER SCIENCE STUDY PROGRAM
DEPARTMENT OF MATHEMATICS
FACULTY OF SCIENCE AND TECHNOLOGY
SANATA DHARMA UNIVERSITY
YOGYAKARTA
2008
ABSTRAK
Minimum Spanning Tree adalah salah satu kasus dalam pemrograman
matematika yang mempunyai banyak manfaat dalam kehidupan sehari-hari.
Misalnya dalam sistem sarana transportasi dan routing pada jaringan komputer.
Namun begitu, belum banyak yang mengetahui perihal metode minimum
spanning tree ini. Tujuan dari penulisan ini adalah untuk membangun sistem
simulasi yang dapat mempermudah pemahaman teori Minimum Spanning Tree.
Tugas akhir ini menggunakan algoritma Kruskal untuk menyelesaikan
permasalahan minimum spaning tree. Sistem Simulasi Minimum Spanning Tree
menggunakan algoritma Kruskal dibangun dengan metode waterfall dengan
menggunakan bahasa pemrograman Visual Basic .Net.
Hasil akhir dari pembuatan program, program dapat digunakan untuk
menyelesaikan permasalahan minimum spaning tree dengan meminimumkan
bobot dan dengan batasan jumlah titik sebanyak dua belas titik. Sistem simulasi
ini dapat memvisualisasikan proses pencarian minimum spanning tree. Selain itu
sistem juga dapat menyimpan data yang telah dimasukkan oleh user. Data yang
disimpan meliputi titik, relasi antar titik, dan bobot.
iv
ABSTRACT
Minimum Spanning Tree is one of cases in mathematics programming
which has a lot of advantages in our daily life. For examples are on the
transportation system and computer network routing. Nevertheless, not all of the
people know about this method. The purpose of this writing is to build a
simulation system which can make minimum spanning tree theory easier.
The final project uses Kruskal’s algorithm to solve minimum spanning tree
problem. Simulation of Minimum spanning tree system using Kruskal’s algorithm
is built with the waterfall method and it uses Visual Basic .Net programming
language.
The result is the application can be used to solve the minimum spanning
tree problem by minimizing the weight and by limiting the number of vertex
becomes 12 vertexes. This simulation system can visualize the minimum spanning
tree searching process. Besides, the system can save the data which has been
entered by users. The saved data include vertex, edge, and the weight.
v
PERNYATAAN KEASLIAN KARYA
Saya menyatakan dengan sesungguhnya bahwa skripsi yang saya tulis ini
tidak memuat karya atau bagian dari karya orang lain, kecuali yang telah
disebutkan dalam kutipan dan daftar pustaka, sebagaimana layaknya karya ilmiah.
Yogyakarta, 30 September 2008
Penulis,
Rina Pertiwi Suherman
vii
KATA PENGANTAR
Puji dan syukur penulis panjatkan kepada Tuhan Yang Maha Esa karena
karunia-Nya sehingga tugas akhir ini dapat diselesaikan. Tugas akhir ini disusun
untuk memenuhi salah satu syarat memperoleh gelar sarjana strata satu program studi
Ilmu Komputer Fakultas Sains dan Teknologi Universitas Sanata Dharma
Yogyakarta.
Tugas akhir dengan judul “Simulasi Minimum Spanning Tree Menggunakan
Algoritma Kruskal” diharapkan dapat bermanfaat bagi Program Studi Ilmu Komputer
FST Universitas Sanata Dharma sebagai lembaga studi ilmu terkait.
Banyak kendala-kendala yang dihadapi dalam menyelesaikan tugas akhir ini,
namun berkat adanya bantuan, bimbingan dan kerjasama maka tugas akhir akhirnya
dapat selesai. Oleh karena itu penulis mengucapkan terima kasih kepada:
1. Romo Dr. Ir. P. Wiryono P.,SJ. selaku Rektor Universitas Sanata Dharma.
2. Romo Ir. Greg. Heliarko SJ.,SS.,B.ST.,M.Sc.,MA. selaku Dekan Fakultas
Sains dan Teknologi.
3. Ibu P.H. Prima Rosa, S.Si.,M.Sc. selaku Ketua Jurusan Matematika dan Ketua
Program Studi Ilmu Komputer sekaigus sebagai dosen pembimbing akademik
atas bimbingannya selama masa perkuliahan..
viii
4. Bapak Y. Joko Nugroho,S.Si. selaku dosen pembimbing yang telah
membimbing penulis selama menyelesaikan tugas akhir.
5. Orang tua, kakak dan adik serta keluarga atas dukungan materi dan moral.
6. Teman-teman prodi Ilmu Komputer yang telah membantu dalam banyak hal
yang tidak dapat disebutkan satu per satu.
7. Semua pihak yang telah memberikan dukungan secara langsung dan tidak
langsung.
Tentunya tugas akhir ini belum sempurna, maka kritik dan saran yang.
membangun dari semua pihak sangat diharapkan.
Yogyakarta, 30 September 2008
Penulis,
Rina Pertiwi Suherman
ix
DAFTAR ISI
HALAMAN JUDUL ....................................................................................... i
HALAMAN PERSETUJUAN ........................................................................ ii
HALAMAN PENGESAHAN ......................................................................... iii
ABSTRAK ...................................................................................................... iv
ABSTRACT .................................................................................................... v
LEMBAR PERNYATAAN PERSETUJUAN .............................................. vi
PERNYATAAN KEASLIAN KARYA ......................................................... vii
KATA PENGANTAR .................................................................................... viii
DAFTAR ISI ................................................................................................... x
DFTAR TABEL .............................................................................................. xiv
DAFTAR GAMBAR ...................................................................................... xv
BAB I PENDAHULUAN
A. Latar Belakang Masalah ...................................................................... 1
B. Rumusan Masalah ............................................................................... 2
C. Batasan Masalah ................................................................................. 3
D. Tujuan Penulisan ................................................................................. 3
E. Manfaat Penulisan ............................................................................... 3
F. Metode Penulisan ................................................................................ 4
G. Sistematika Penulisan ......................................................................... 5
BAB II LANDASAN TEORI
A. Graf ..................................................................................................... 6
x
1. Sejarah Graf .................................................................................. 6
2. Teori Graf
a. Defenisi Graf ........................................................................... 8
b. Jenis Graf ................................................................................ 10
B. Pohon (Tree)
1. Defenisi Pohon .............................................................................. 14
2. Terminologi Pada Pohon Berakar ................................................. 16
3. Pohon Merentang (Spanning Tree) dan Pohon Merentang
Minimum (Minimum Spanning Tree) ........................................... 18
C. Algoritma Kruskal ............................................................................... 20
1. Cara Kerja Algoritma Kruskal ...................................................... 21
2. Ilustrasi Cara Kerja Algoritma Kruskal ........................................ 22
D. Struktur Data
1. Array ............................................................................................. 26
2. Class .............................................................................................. 27
3. Method Drawline .......................................................................... 27
BAB III ANALISIS DAN PERANCANGAN SISTEM
A. Analisis Sistem .................................................................................... 29
B. Perancangan Sistem
1. Konsep Kerja Sistem ..................................................................... 30
2. Struktur Data ................................................................................. 31
3. Algoritma dan Flowchart
a. Flowchart Algoritma Kruskal ................................................. 34
xi
b. Flowchart Algoritma Sistem ................................................... 35
C. Perancangan Antarmuka ..................................................................... 36
1. Tampilan Awal ............................................................................... 37
2. Tampilan Utama ............................................................................. 38
3. Tampilan Form Input dan Hasil ..................................................... 38
4. Perancangan Penyimpanan ............................................................. 40
BAB IV IMPLEMENTASI DAN PEMBAHASAN
A. Implementasi Program
1. Algoritma Kruskal .......................................................................... 41
2. Proses Penyimpanan Data Verteks ................................................. 44
3. Proses Open Data Verteks .............................................................. 45
4. Proses Gambar Graf ....................................................................... 46
B. Implementasi Antarmuka
1. Tampilan Awal ............................................................................... 48
2. Tampilan Utama ............................................................................. 48
3. Tampilan Form Input dan Hasil ..................................................... 50
4. Tampilan Open ............................................................................... 52
5. Tampilan Save ................................................................................ 52
C. Pembahasan ......................................................................................... 53
1. Contoh Penyelesaian Masalah MST ............................................... 53
D. Analisa
1. Kelebihan Program ......................................................................... 57
2. Kekurangan Program ...................................................................... 58
xii
BAB V PENUTUP
A. Kesimpulan ......................................................................................... 59
B. Saran .................................................................................................... 59
xiii
DAFTAR TABEL
Tabel 2.1 Jenis-Jenis Graf ............................................................................... 14
Table 3.1 Data Ujicoba ................................................................................... 54
Tabel 3.2 Data Ujicoba yang telah di sorting .................................................. 54
Tabel 3.3 Hasil Pencarian MST untuk data ujicoba ........................................ 57
xiv
DAFTAR GAMBAR
Gambar 2.1 Jembatan Konigsberg dan representasinya dalam graf ............... 6
Gambar 2.2 Graf sederhana, graf ganda, dan graf semu ................................. 9
Gambar 2.3 Graf tak berhingga ....................................................................... 12
Gambar 2.4 Graf berarah ................................................................................. 14
Gambar 2.5 Ikatan Kimia ................................................................................ 15
Gambar 2.6 Struktur Pertandingan Sistem gugur ........................................... 15
Gambar 2.7 Pohon berakar .............................................................................. 16
Gambar 2.8 Subree pada pohon berakar ......................................................... 17
Gambar 2.9 Contoh graf beserta pohon rentangnya ........................................ 19
Gambar 2.10 Aplikasi pohon merentang pada jaringan komputer ................. 19
Gambar 2.11 Graf ABCDEFG ........................................................................ 22
Gambar 2.12 Tahap pertama penerapan algoritma Kruskal
pada graf ABCDEFG ................................................................ 22
Gambar 2.13 Tahap kedua penerapan algoritma Kruskal
pada graf ABCDEFG ................................................................ 23
Gambar 2.14 Tahap ketiga penerapan algoritma Kruskal
pada graf ABCDEFG ................................................................ 23
Gambar 2.15 Tahap keempat penerapan algoritma Kruskal
pada graf ABCDEFG ................................................................ 24
Gambar 2.16 Tahap kelima penerapan algoritma Kruskal
xv
pada graf ABCDEFG ................................................................. 25
Gambar 2.17 Minimum Spanning Tree dari graf ABCDEFG ........................ 25
Gambar 3.1 Flowchart algoritma Kruskal ....................................................... 34
Gambar 3.2 Flowchart system Simulasi MST dengan
algoritma Kruskal ........................................................................ 35
Gambar 3.3 Rancangan Struktur Menu ........................................................... 37
Gambar 3.4 Rancangan tampilan menu startup .............................................. 37
Gambar 3.5 Rancangan tampilan utama ......................................................... 38
Gambar 3.6 Rancangan Form Input dan Hasil ................................................ 39
Gambar 4.1 Tampilan awal ............................................................................. 48
Gambar 4.2 Tampilan utama ........................................................................... 50
Gambar 4.3 Form Input dan Hasil .................................................................. 50
Gambar 4.4 Tampilan Open ............................................................................ 52
Gambar 4.5 Tampilan Save ............................................................................. 53
Gambar 4.6 Proses pertahap pembentukan graf MST ..................................... 56
xvi
BAB I
PENDAHULUAN
A. Latar Belakang Masalah
Teori Graf adalah salah satu teori yang sudah tua usianya, namun masih
terus dibahas dan dikembangkan, karena memiliki banyak terapan. Graf
merupakan salah satu metode untuk menyelesaikan permasalahan diskrit dalam
dunia nyata, yaitu dapat digunakan untuk merepresentasikan objek-objek diskrit
dan hubungan antara objek-objek tersebut. Salah satu contoh representasi visual
dari graf adalah peta. Banyak hal yang dapat digali dari reperesentasi tersebut,
misalnya untuk menentukan tata letak jalur transportasi, menentukan jalur
terpendek dari satu tempat ke tempat lain, dan sebagainya.
Beberapa masalah yang berkaitan dengan graf yang ditemukan manusia
dalam kehidupan nyata kemudian memunculkan konsep-konsep pemecahan
masalah graf. Salah satu konsep graf adalah konsep pohon (tree). Konsep ini
merupakan konsep yang paling populer dan penting, karena konsep pohon mampu
mendukung pemecahan masalah dalam berbagai terapan graf. Konsep pohon
digunakan sejak tahun 1875 oleh seorang matematikawan yang berasal dari
Inggris, Arthur Caylay untuk menghitung jumlah senyawa kimia. (Doni Arzinal,
2006)
Di dalam konsep pohon sendiri terdapat banyak jenis pohon yang digunakan
untuk menyelesaikan masalah dalam dunia terapan graf, salah satunya adalah
penggunaan pohon merentang atau Spanning Tree. Aplikasi Spanning Tree
2
misalnya pada pemeliharaan jalur rel kereta api. Dengan Spanning Tree,
perusahaan kereta api dapat memodelkan alokasi dana secara optimal dengan
mencari jalur pemeliharaan dengan bobot biaya yang minimum. Spanning Tree
juga memainkan peranan penting dalam jaringan komputer, travelling salesman
problem, dan lain-lain. Apabila Spanning Tree diterapkan pada persoalan yang
mengandung unsur pencarian bobot yang minimum maka dinamakan Minimum
Spanning Tree (MST). Adapun algoritma yang akan digunakan untuk
menyelesaikan masalah Minimum Spanning Tree dalam penulisan ini adalah
algoritma Kruskal.
Minimum Spanning Tree merupakan teori yang sangat bermanfaat untuk
membantu pekerjaan manusia dalam kehidupan sehari-hari. Sehingga teori ini
sangat penting untuk dipelajari. Namun begitu, tidak banyak yang mengetahui
perihal cara kerja Minimum Spanning Tree ini. Maka, untuk mempermudah dalam
mempelajari dan memahami teori ini, saya akan memvisualisasikan vertek atau
titik, garis penghubung, beserta bobotnya ke dalam suatu graf, dan kemudian
menampilkan proses pencarian pohon rentang minimum graf tersebut secara
bertahap, sehingga terbentuk pohon merentang minimum.
B. Rumusan Masalah
Bagaimana membuat sebuah sistem yang dapat memvisualisasikan masalah
Minimum Spanning Tree dengan menggunakan algoritma Kruskal.
3
C. Batasan Masalah
1. Tidak ada batasan jumlah derajat
2. Jumlah vertek dibatasi sebanyak 12 vertek
3. Sistem ini dapat digunakan untuk mencari minimum spanning tree pada
graf tidak berarah.
4. Ada biaya / bobot dari setiap edge (rusuk).
5. Input / Output
- Input dari user berupa :
jumlah vertek (titik/simpul), hubungan antara vertek yang akan
membentuk edge (rusuk), dan bobot setiap rusuk.
- Output berupa:
pohon rentang minimum dengan biaya/bobot terkecil beserta tampilan
hasil pohon rentang minimumnya.
D. Tujuan Penulisan
Mengimplementasikan dan memvisualisasikan permasalahan Minimum
Spanning Tree dengan algoritma Kruskal ke dalam sofware dengan menggunakan
bahasa pemrograman Visual Basic .Net
E. Manfaat Penulisan
Dapat memvisualisasikan masalah Minimum Spanning Tree dengan
menemukan tree dari sebuah graph dengan bobot seminimal mungkin
menggunakan algoritma Kruskal yang diimplementasikan dalam software.
4
F. Metode Penulisan
Metode yang digunakan untuk mengembangkan sistem simulasi Minimum
Spanning Tree menggunakan algoritma Kruskal ini adalah rekayasa perangkat
lunak dengan metode waterfall. Adapun langkah-langkah yang dilakukan adalah
sebagai berikut :
1. Analisis
Pada tahap ini, penulis mengumpulkan data – data yang diperlukan
dalam pembuatan sistem ini, yang diantaranya meliputi kebutuhan
pemakai, fungsi/prosedur, antarmuka, dan unjuk kerja perangkat lunak.
2. Rancangan
Penulis mengubah kebutuhan pada tahap analisis menjadi sebuah
representasi program yang dapat dimengerti sebelum proses
implementasi. Langkah ini memusatkan kerja pada struktur data,
arsitektur dan prosedur detil, dan karakteristik antarmuka.
3. Implementasi
Penulis menerjemahkan rancangan dalam bentuk yang dapat dibaca
oleh mesin.
4. Pengujian
Penulis mencari kemungkinan - kemungkinan kesalahan dan
memeriksa apakah hasil sudah sesuai dengan yang diinginkan.
5
G. Sistematika Penulisan
BAB I PENDAHULUAN
Membahas tentang latar belakang masalah, perumusan masalah,
batasan masalah, tujuan penulisan, manfaat penulisan, metode
penulisan, sistematika penulisan.
BAB II LANDASAN TEORI
Bab ini berisi tentang landasan teori yang digunakan sebagai dasar
untuk membangun sistem simulasi minimum spanning tree
menggunakan algoritma Kruskal.
BAB III ANALISIS DAN PERANCANGAN SISTEM
Bab ini berisi tentang gambaran sistem dan kebutuhan sistem yang
akan dibuat, meliputi flowchart sistem dan desain antarmuka
pengguna sistem.
BAB IV IMPLEMENTASI
Bab ini berisi tentang impementasi algoritma Kruskal, desain dan
proses pada sistem simulasi Minimum Spanning Tree
menggunakan algoritma Kruskal.
BAB V PENUTUP
Bab ini berisi tentang kesimpulan dan saran dari pembahasan dan
perancangan yang telah dilakukan dalam penulisan tugas akhir ini.
BAB II
DASAR TEORI
A. Graf
Graf merupakan salah satu cabang ilmu dalam ilmu matematika yang
mengulas masalah titik dan garis. Teori graf dapat dimanfaatkan dalam berbagai
hal, misalnya untuk merancang jaringan komputer atau sistem prasarana
transportasi. Masalah yang paling sering muncul adalah bagaimana mencari
lintasan dengan bobot minimum yang menghubungkan beberapa wilayah yang
memiliki bobot yang berbeda-beda.
1. Sejarah Graf
Sesuai dengan catatan sejarah, masalah yang pertama kali menggunakan
penerapan teori graf adalah masalah jembatan Königsberg (tahun 1736). Di
sebuah kota bernama Königsberg (sebelah timur Prussia, Jerman sekarang),
sekarang bernama kota Kaliningrad, terdapat sungai Pregal yang mengalir
mengitari pulau Kneiphof lalu bercabang menjadi dua buah anak sungai.
Gambar 2.1 (a) Jembatan Konigsberg dan (b) representasinya dalam graf
(Deasy Ramadiyan Sari, 2006 )
7
Ada tujuh buah jembatan yang menghubungkan daratan yang dibelah oleh
sungai tersebut. Permasalahan dari jembatan Königsberg adalah: apakah mungkin
melalui ketujuh buah jembatan itu masing-masing tepat satu kali, dan kembali lagi
ke tempat semula? Sebagian penduduk kota berpendapat bahwa tidak mungkin
melalui setiap jembatan itu hanya sekali dan kembali lagi ke tempat asal mula
keberangkatan, tetapi mereka tidak dapat menjelaskan alasan dari jawaban
tersebut, kecuali dengan cara coba-coba.
Kemudian pada tahun 1736, L.Euler, seorang matematikawan Swiss, adalah
orang pertama yang berhasil menemukan jawaban masalah itu dengan pembuktian
yang sederhana. Ia memodelkan masalah ini ke dalam graph. Daratan (titik-titik
yang dihubungkan oleh jembatan) dinyatakannya sebagai titik yang disebut titik
(vertex) dan jembatan dinyatakan sebagai garis yang disebut rusuk (edge). Setiap
titik diberi label huruf A, B, C, dan D. Graph yang dibuat oleh Euler diperlihatkan
pada Gambar 2.1.b.
Jawaban yang dikemukakan oleh Euler adalah : orang tidak mungkin
melalui ketujuh jembatan itu masing-masing satu kali dan kembali lagi ke tempat
asal keberangkatan jika derajat setiap titik tidak seluruhnya genap. Yang
dimaksud dengan derajat adalah banyaknya rusuk yang bersisian dengan titik.
Sebagai contoh, pada gambar 2.1.b titik C memiliki derajat 3 karena ada tiga buah
rusuk yang bersisian dengannya, titik B dan D juga berderajat dua, sedangkan titik
A berderajat 5. Karena tidak semua titik berderajat genap, maka tidak mungkin
dilakukan perjalananan berupa sirkuit (yang dinamakan dengan sirkuit Euler)
pada graf tersebut.
8
2. Teori Graf
a. Definisi Graf
Secara matematis, graf didefinisikan sebagai berikut, misalnya Graf ( G)
didefinisikan sebagai pasangan himpunan (V, E), yang dalam hal ini:
V = himpunan tidak-kosong dari titik-titik (vertex)
= { v1 , v2 , ... , vn }
E = himpunan rusuk (edges) yang menghubungkan sepasang titik
= {e1 , e2 , ... , en } atau dapat ditulis singkat notasi G = (V, E).
Definisi di atas menyatakan bahwa V tidak boleh kosong, sedangkan E boleh
kosong. Jadi, sebuah graf dimungkinkan tidak mempunyai rusuk satu buah pun,
tetapi titiknya harus ada, minimal satu. Graf yang hanya mempunyai satu buah
titik tanpa sebuah rusuk pun dinamakan graf trivial.
Titik pada graf dapat dinomori dengan huruf, seperti a, b, c, …, v, w, ...,
dengan bilangan asli 1, 2, 3, ..., atau gabungan keduanya. Sedangkan rusuk yang
menghubungkan titik vi dengan titik vj dinyatakan dengan pasangan (vi, vj) atau
dengan lambang e1, e2, …. Dengan kata lain, jika e adalah rusuk yang
menghubungkan titik vi dengan titik vj , maka e dapat ditulis sebagai e = (vi , vj)
Secara geometri graf digambarkan sebagai sekumpulan titik (vertex) di
dalam bidang 2 dimensi yang dihubungkan dengan sekumpulan rusuk (edges).
9
Gambar 2.2 Graf sederhana (G1), ganda (G2), semu (G3)
Gambar 2.2 memperlihatkan tiga buah graf, yaitu graf G1, graf G2, dan graf
G3.
Graf G1 adalah graf dengan himpunan titik V dan himpunan rusuk E adalah
V = { 1, 2, 3, 4 }
E = { (1, 2), (1, 3), (2, 3), (2, 4), (3, 4) }
Graf G2 adalah graf dengan himpunan titik V dan himpunan rusuk E adalah:
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4) }
himpunan ganda
= { e1, e2, e3, e4, e5, e6, e7}
Graf G3 adalah graf dengan himpunan titik V dan himpunan rusuk E adalah:
V = { 1, 2, 3, 4 }
E = { (1, 2), (2, 3), (1, 3), (1, 3), (2, 4), (3, 4), (3, 4), (3, 3) }
himpunan ganda
= { e1, e2, e3, e4, e5, e6, e7, e8}
10
Pada graf G2 , rusuk e3 = (1, 3) dan rusuk e4 = (1, 3) dinamakan rusuk-ganda
(multiple edges atau paralel edges) karena kedua rusuk ini menghubitikungkan
dua buah yang sama, yaitu titik 1 dan titik 3. Pada graf G3, rusuk e8 = (3, 3)
dinamakan gelang atau kalang (loop) karena ia berawal dan berakhir pada titik
yang sama.
b. Jenis Graf
Graf dapat dikelompokkan menjadi beberapa kategori bergantung pada
sudut pandang pengelompokannya. Pengelompokan graf dapat dipandang
berdasarkan ada tidaknya rusuk ganda, berdasarkan jumlah titil, atau berdasarkan
orientasi arah pada rusuk.
Berdasarkan ada tidaknya gelang atau rusuk ganda pada suatu graf, maka
secara umum graf dapat digolongkan menjadi dua jenis:
i. Graf sederhana (simple graph).
Graf yang tidak mengandung gelang maupun rusuk-ganda dinamakan
graf sederhana. Graf G1 pada Gambar 2.2 adalah contoh graf sederhana
yang merepresentasikan jaringan komputer. Titik menyatakan komputer,
sedangkan rusuk menyatakan saluran telepon untuk berkomunikasi.
Saluran telepon dapat beroperasi pada dua arah.
11
ii. Graf tak-sederhana (unsimple-graph).
Graf yang mengandung rusuk ganda atau gelang dinamakan graf tak-
sederhana (unsimple graph). Ada dua macam graf tak-sederhana, yaitu
graf ganda (multigraph) dan graf semu (pseudograph). Graf ganda
adalah graf yang mengandung rusuk ganda. rusuk ganda yang
menghubungkan sepasang titik bisa lebih dari dua buah. Graf G2 pada
Gambar 2.2 adalah graf-ganda, rusuk ganda pada graf G2 dapat
diandaikan sebagai saluran telepon tambahan apabila beban komunikasi
data antar komputer sangat padat.
Graf semu adalah graf yang mengandung gelang. Graf G3 pada Gambar
2.2 adalah graf semu (termasuk bila memiliki rusuk ganda sekalipun).
Rusuk gelang pada graf G3 dapat dianggap sebagai saluran telepon
tambahan yang menghubungkan komputer dengan dirinya sendiri. Graf
semu lebih umum daripada graf ganda, karena rusuk pada graf semu
dapat terhubung ke dirinya sendiri.
Jumlah titik pada graf disebut sebagai kardinalitas graf, dan dinyatakan
dengan n = |V|, dan jumlah rusuk dinyatakan dengan m = |E|. Pada
contoh di atas, graf G1 mempunyai n = 4, dan m = 4, sedangkan graf G2
mempunyai n = 3 dan m = 4.
12
Berdasarkan jumlah titik pada suatu graf, maka secara umum graf dapat
digolongkan menjadi dua jenis:
i. Graf berhingga (limited graph)
Graf berhingga adalah graf yang jumlah titiknya, n berhingga. Graf pada
Gambar 2.2 adalah contoh graf yang berhingga.
ii. Graf tak-berhingga (unlimited graph)
Graf yang jumlah titiknya, n tidak berhingga banyaknya disebut graf tak-
berhingga. Dua buah graf pada Gambar 2.3 di bawah adalah contoh graf
yang tidak berhingga.
Gambar 2.3 Dua buah graf tak-berhingga
Rusuk pada graf dapat mempunyai orientasi arah. Berdasarkan orientasi arah
pada rusuk, maka secara umum graf dibedakan atas 2 jenis, yaitu sebagai berikut:
13
i. Graf tak-berarah (undirected graph)
Graf yang rusuknya tidak mempunyai orientasi arah disebut graf tak-
berarah. Pada graf tak-berarah, urutan pasangan titik yang dihubungkan
oleh rusuk tidak diperhatikan. Jadi, (vj , vk) = (vk , vj) adalah rusuk yang
sama. Tiga buah graf pada Gambar 2.2 adalah graf tak-berarah.
ii. Graf berarah (directed graph atau digraph)
Graf yang setiap rusuknya diberikan orientasi arah disebut sebagai graf
berarah. Rusuk berarah ini biasa disebut dengan busur (arc). Pada graf
berarah, (vj, vk) dan (vk, vj) menyatakan dua buah busur yang berbeda,
dengan kata lain (vj, vk) ≠ (vk , vj). Untuk busur (vj, vk), titik vj dinamakan
titik asal (initial vertex) dan titik vk dinamakan titik terminal (terminal
vertex). Graf G4 pada Gambar 2.4 adalah contoh graf berarah. Pada graf
G4 diandaikan saluran telepon tidak dapat beroperasi pada dua arah.
Saluran hanya beroperasi pada arah yang ditunjukkan oleh anak panah.
Jadi, sebagai contoh, saluran telepon (1, 2) tidak sama dengan saluran
telepon (2, 1). Graf berarah sering dipakai untuk menggambarkan aliran
proses, peta lalu lintas suatu kota (jalan searah atau dua arah), dan
sebagainya. Pada graf berarah, gelang diperbolehkan, tetapi rusuk ganda
tidak.
14
Gambar 2.4 Graf berarah
Definisi graf dapat diperluas sehingga mencakup graf-ganda berarah. Pada
graf-ganda berarah, gelang dan rusuk ganda diperbolehkan ada. Graf G5 pada
Gambar 2.4 adalah contoh graf-ganda berarah. Tabel 2.1 meringkas perluasan
definisi graf.
Tabel 2.1 Jenis-jenis graf
Jenis Rusuk Rusuk ganda dibolehkan?
Rusuk gelang dibolehkan?
Graf sederhana Tak berarah Tidak Tidak
Graf ganda Tak berarah Ya Tidak
Graf semu Tak berarah Ya Ya
Graf berarah Berarah Tidak Ya
Graf ganda berarah Berarah Ya Ya
B. Pohon (Tree)
1. Definisi Pohon
Pohon didefinisikan sebagai suatu graf tak berarah yang terhubung
(connected undirected graph), dan tidak mengandung rangkaian
15
sederhana(cycle/sirkuit). Pohon adalah bentuk khusus dari suatu graf yang banyak
diterapkan untuk berbagai keperluan. Misalnya struktur organisasi suatu
perusahaan, silsilah suatu keluarga, skema sistem gugur suatu pertandingan, dan
ikatan kimia suatu molekul adalah jenis graf yang tergolong sebagai pohon. Pada
pohon, titik-titik yang berderajat satu dinamakan daun (leave), sedangkan titik
yang derajatnya lebih besar daripada satu dinamakan titik cabang (branch node)
atau titik internal (internal node) dan kumpulan pohon-pohon yang terpisahkan
satu sama lain disebut hutan (forest). Contoh pohon (tree) dapat dilihat pada
gambar 2.5 dan 2.6.
Gambar 2.5 Ikatan Kimia
Gambar 2.6 Struktur Pertandingan Sistem gugur
16
2. Terminologi pada pohon berakar
a. Anak (child atau children) dan Orangtua (parent)
Anak adalah titik setelah suatu titik dalam pohon. Dari gambar 2.7
diketahui b, c, dan d adalah anak-anak titik a, dan orang tua adalah titik
sebelum suatu titik lain dalam satu pohon, jadi a adalah orangtua dari anak-
anak tersebut.
Gambar 2.7 Pohon Berakar
b. Lintasan (path)
Lintasan adalah jalur yang harus ditempuh dari suatu titik ke titik
lainnya. Panjang lintasan ditentukan dari titik asal. Dari gambar 2.7 diketahui
lintasan dari a ke j adalah a, b, e, j dan panjang lintasan dari a ke j adalah 3.
17
c. Saudara kandung (sibling)
Saudara kandung adalah titik yang mempunyai orangtua yang sama. Dari
gambar 2.7 diketahui f adalah saudara kandung e, tetapi g bukan saudara
kandung e, karena orangtua mereka berbeda.
d. Upapohon (subtree)
Upapohon atau subtree adalah pohon yang dibentuk dengan memotong
pohon yang sudah ada, contoh dapat dilihat pada gambar 2.8.
Gambar 2.8 Subtree pada Pohon Berakar
e. Derajat (degree)
Derajat sebuah titik adalah jumlah upapohon atau jumlah anak pada titik
tersebut, yang dimaksudkan di sini adalah derajat ke bawah atau keluar. Pada
gambar 2.8 derajat a adalah 3, derajat b adalah 2, derajat d adalah satu dan
18
derajat c adalah 0. Derajat sebuah pohon adalah derajat maksimum dari semua
titik derajat pohon itu sendiri. Pohon pada gambar 2.8 berderajat 3.
f. Daun (leaf)
Daun adalah titik paling ujung dalam sebuah pohon. Jadi daun tidak
mempunyai anak dan berderajat 0. titik h, i, j, f, c, l, dan m pada gambar 2.7
adalah daun.
g. Titik Dalam (internal nodes)
Titik yang mempunyai upapohon atau anak disebut titik dalam. Titik b,
d, e, g, dan k pada gambar 2.7 adalah titik dalam.
h. Aras (level) dan Tingkat ketinggian (height) atau Kedalaman (depth)
Aras maksimum dari suatu pohon disebut tinggi atau kedalaman pohon
tersebut. Pohon pada gambar 2.7 mempunyai tinggi 4.
3. Pohon Merentang (Spanning Tree) dan Pohon Merentang Minimum
(Minimum Spanning Tree)
Pohon merentang dari graf terhubung adalah upagraf merentang yang berupa
pohon. Pohon merentang diperoleh dengan memutus sirkuit di dalam graf.
Sehingga setiap graf terhubung mempunyai paling sedikit satu buah pohon
merentang dan graf tak-terhubung dengan k komponen mempunyai k buah hutan
19
merentang yang disebut hutan merentang (spanning forest). Contoh graf beserta
pohon merentangnya dapat dilihat pada gambar 2.9.
Gambar 2.9 Graf G berikut empat macam pohon rentangnya
Contoh aplikasi pohon merentang :
a. Jalan terminimum yang menghubungkan semua kota
b. Perutean (routing) pesan pada jaringan komputer.
c. Multicast
Gambar 2.10 Aplikasi pohon merentang (b) pada jaringan komputer (a)
(Amir Muntaha, 2006)
20
Jika Spanning Tree diterapkan pada persoalan yang mengandung unsur
pencarian bobot yang minimum maka dinamakan Minimum Spanning Tree (MST).
Masalah Minimum Spanning Tree pertama kali diformulasikan oleh seorang
ilmuwan Cekoslavia, Otakar Boruvka pada tahun 1926, yang melahirkan sebuah
algoritma, dikenal dengan Boruvka’s Algorithm. Algoritma ini memberikan solusi
dalam menentukan susunan jaringan kabel listrik yang paling ekonomis. Sejak
saat itu, formulasi Minimum Spanning Tree banyak diterapkan di berbagai
masalah optimasi kombinatoris, seperti masalah transportasi, desain jaringan
telekomunikasi, sistem distribusi, dan lain sebagainya. Masalah-masalah tersebut
pada umumnya dapat dibawa ke bentuk masalah program linear, yang saat ini
telah ditemukan banyak metode untuk menyelesaikannya, antara lain algoritma
waktu polinomial yang dikembangkan oleh Kruskal dan Prim. Penulis hanya akan
membahas dan menggunakan algoritma Kruskal.
C. Algoritma Kruskal
Algoritma Kruskal pertama kali dipopulerkan oleh Joseph Kruskal pada
tahun 1956. Algoritma Kruskal adalah sebuah algoritma dalam teori graf yang
mencari sebuah Minimum Spanning Tree untuk sebuah graf berbobot yang
terhubung. Ini berarti mencari subset dari rusuk yang membentuk sebuah Tree,
yang menampung setiap vertex, dimana total bobot dari semua rusuk dalam Tree
adalah minimum. Algoritma Kruskal merupakan salah satu contoh dari Algoritma
Greedy
21
1. Cara Kerja Algoritma Kruskal
Dalam algoritma ini rusuk-rusuk pada graf dipilih satu-persatu berurutan
dari rusuk dengan bobot terkecil, kemudian saling dihubungkan, dengan ketentuan
saat menghubungkan titik dari setiap rusuk tidak membentuk sirkuit (cycle). Jika
jumlah rusuk yang dihubungkan berjumlah n-1, dimana n adalah jumlah titik,
maka rusuk-rusuk yang telah dihubungkan tadi akan membentuk sebuah tree yang
mempunyai bobot terkecil atau pohon rentang minimum.
Secara formal, algoritma Kruskal dapat dinyatakan sebagai berikut :
Misalkan G adalah graf mula-mula dengan n titik, T adalah pohon rentang
minimum, E adalah himpunan semua rusuk G
a. Isi T dengan semua titik-titik G tanpa garis
b. m = 0
c. Selama m < (n-1) lakukan :
- Tentukan garis e ∈ E dengan bobot minimum. Jika ada beberapa e
dengan sifat tersebut, pilih salah satu secara sembarang
- Hapus e dari E
- Jika e ditambahkan ke T tidak menghasilkan sirkuit, maka
i. Tambahkan e ke T
ii. M = m + 1
22
2. Ilustrasi Cara Kerja Algoritma Kruskal
a. Misalnya, graf pada Gambar 2.11 adalah graf awal, yaitu graf
ABCDEFG. Angka-angka di dekat garis penghubung / rusuk adalah
bobotnya.
Gambar 2.11 Graf ABCDEFG
b. Dari semua bobot yang ada, bobot paling kecil adalah 5. Yaitu AD dan
CE. AD ditetapkan sebagai rusuk awal, maka diberi highlight hijau
(gambar 2.12).
Gambar 2.12 Tahap pertama penerapan algoritma Kruskal
23
c. Selain AD, rusuk yang berbobot 5 adalah CE. Oleh karena itu CE
diberi highlight hijau. Maka rusuk yang sudah dipilih sebagai bagian
dari jalur MST pada graf ABCDEFG adalah AD-CE (gambar 2.13).
Gambar 2.13 Tahap kedua penerapan algoritma Kruskal
d. Karena semua rusuk berbobot 5 sudah dipilih, bobot yang dipilih
selanjutnya adalah bobot yang lebih besar dari bobot sebelumnya,
yaitu 6. Rusuk yang mempunyai bobot 6 adalah DF. DF diberi
highlight hijau. Maka rusuk yang sudah dipilih sebagai bagian dari
jalur MST pada graf ABCDEFG adalah AD-CE-DF (gambar 2.14).
Gambar 2.14 Tahap ketiga penerapan algoritma Kruskal
24
e. Rusuk yang dipilih selanjutnya adalah rusuk yang mempunyai bobot
lebih besar dari bobot sebelumnya, yaitu 7. Rusuk yang mempunyai
bobot 7 adalah rusuk AB, maka AB diberi highlight hijau. Dengan
dipilihnya rusuk AB ini, bisa ditentukan bahwa rusuk BD akan
membentuk sebuah sirkuit. Maka BD diberi highlight merah, artinya
tidak akan ditambahkan ke dalam MST. Rusuk yang sudah dipilih
sebagai bagian dari jalur MST pada graf ABCDEFG adalah AD-CE-
DF-AB (gambar 2.15).
Gambar 2.15 Tahap keempat penerapan algoritma Kruskal
f. Selain AB, rusuk yang berbobot 7 adalah BE. Oleh karena itu BE
diberi highlight hijau. Dengan dipilihnya rusuk BE ini, bisa ditentukan
bahwa rusuk BC, DE dan EF dapat membentuk sirkuit. Maka rusuk
BC, DE dan EF diberi highlight merah, artinya tidak akan ditambahkan
ke dalam MST. Rusuk yang sudah dipilih sebagai bagian dari jalur
MST pada graf ABCDEFG adalah AD-CE-DF-AB-BE (gambar 2.16).
25
Gambar 2.16 Tahap kelima penerapan algoritma Kruskal
g. Rusuk yang dipilih selanjutnya adalah rusuk yang berbobot lebih besar
dari bobot sebelumnya, yaitu 8. Rusuk yang mempunyai bobot 8
adalah BC dan EF, namun karena kedua rusuk ini dapat membentuk
sirkuit (sudah diberi highlight merah) maka rusuk BC dan EF tidak
akan ditambahkan pada jalur MST. Sehingga rusuk yang dipilih
berikutnya adalah yang mempunyai bobot 9, yaitu EG. Maka EG
diberi highlight hijau. Karena semua titik sudah terhubung, maka
proses pemilihan rusuk dengan bobot terkecil selesai. Dan MST yang
terbentuk dari graf ABCDEFG ini adalah AD-CE-DF-AB-BE-EG,
dengan jumlah bobot 39 (Gambar 2.17).
Gambar 2.17 Minimum Spanning Tree dari graf ABCDEFG
26
D. Struktur Data
1. Array
MST yang merupakan terapan dari teori graph sangat berkaitan dengan
matriks dalam menyelesaikan persoalan didalamnya. Dengan program ini maka
sangatlah tepat untuk menggunakan tipe data Array. Selain itu, juga karena dalam
program ini dibutuhkan data yang besar.
Array adalah suatu tipe data terstruktur yang berupa sejumlah data sejenis
(bertipe data sama) yang jumlahnya tetap dan diberi suatu nama tertentu. Elemen-
elemen array tersusun secara sekuensial di dalam memori sehingga memiliki
alamat yang berdekatan. Array dapat berupa array 1 dimensi, 2 dimensi, bahkan n-
dimensi. Elemen-elemen array bertipe data sama tapi bisa bernilai sama atau
berbeda-beda
Bentuk umum dari deklarasi tipe data array 1 dimensi adalah:
Dim nama_array(dimensi array) As tipe data
nama_array adalah nama dari array yang akan dibuat, dimensi array
yaitu dimensi array yang akan dibuat (1 dimensi, 2 dimensi, ... n dimensi).
Sedangkan tipe data adalah tipe data dari array tersebut (Double, Long,
Integer, String, dll).
Contoh deklarasi tipe data array 1 dimensi:
Dim strMyFriends() As String
Dari contoh deklarasi tipe data array 1 dimensi diatas dapat kita ketahui
sebuah array 1 dimensi dengan nama strMyFriends bertipe data String.
27
Contoh deklarasi tipe data array multidimensi:
Dim atmospherePressures( , , , ) As Short
Dari contoh deklarasi array multidimensi diatas dapat diketahui sebuah array
multidimensi (4 dimensi) dengan nama atmospherePressures bertipe data
Short.
2. Class
Class adalah tipe data yang didalamnya dapat berisi kumpulan berbagai tipe
variabel maupun method.
Contoh deklarasi Class :
Public Class ShowMe Sub ShowFrm() Dim frmNew As Form1 frmNew = New Form1 frmNew.Show() End Sub End Class
Dari contoh class diatas, dapat kita lihat nama class adalah ShowMe.
Kemudian diikuti statemen-statemen, dimana statement-statement tersebut dapat
berupa variabel maupun method.
3. Method DrawLine
Method DrawLine adalah method dalam VB .Net yang digunakan untuk
menggambar garis untuk menghubungkan dua titik.
Contoh penggunaan method DrawLine adalah sebagai berikut :
Public Sub DrawLinePoint(ByVal e As PaintEventArgs) Dim blackPen As New Pen(Color.Black, 3)
28
Dim point1 As New Point(100, 100) Dim point2 As New Point(500, 100) e.Graphics.DrawLine(blackPen, point1, point2) End Sub
Pen adalah parameter yang dapat digunakan untuk menentukan warna, lebar,
dan style dari garis yang akan dibuat. Sedangkan point1 dan point2 adalah letak
koordinat kedua titik yang akan dihubungkan dengan garis tersebut.
BAB III
ANALISIS DAN PERANCANGAN SISTEM
A. Analisis Sistem
Sistem yang akan dikembangkan adalah sistem pencarian minimum
spanning tree dari suatu graf tidak berarah, dengan menggunakan algoritma
Kruskal. Sistem ini disertai dengan visualisasi proses pencarian minimum
spanning tree, sehingga dapat mempermudah pengguna / user dalam memahami
proses pencarian atau pembentukan minimum spanning tree tersebut, tentunya
dengan algoritma yang telah ditentukan, yaitu algoritma Kruskal.
Untuk menentukan minimum spanning tree dari suatu graf tidak berarah,
sistem ini membutuhkan beberapa input data yaitu : jumlah titik / vertex, jumlah
rusuk /edge, hubungan antara dua titik yang akan membentuk sebuah rusuk,
beserta jumlah bobot / biayanya.
1. Kebutuhan Sistem
a. Kebutuhan software dan hardware untuk pengembangan sistem
i. Kebutuhan software
− Sistem operasi : Windows XP Service Pack 2
− Program Aplikasi : Visual Basic .Net, Visual Frame Work
ii. Kebutuhan hardware
− Prosesor Pentium 4
− Memori minimal 128 MB
30
− Hard disk minimal 1 GB
− Alat input berupa keyboard dan mouse
− Alat output berupa monitor dan printer
b. Kebutuhan software dan hardware untuk penggunaan sistem
i. Kebutuhan software minimal
− Sistem operasi : Windows XP Service Pack 2
− Program Aplikasi : Visual Frame Work
ii. Kebutuhan hardware minimal
− Prosesor Pentium 4
− Memori minimal 128 MB
− Hardisk minimal 1 GB
− Alat input berupa keyboard dan mouse
− Alat output berupa monitor
B. Perancangan Proses
1. Konsep Kerja Sistem
Sistem bekerja dengan prinsip aplikasi desktop. Aplikasi dapat langsung
diakses oleh user melalui komputer yang telah terinstal program aplikasi. Pada
saat user mengakses tool untuk mencari minimum spanning tree, maka sistem
akan menjalankan algoritma Kruskal untuk melakukan proses pencarian minimum
spanning tree tersebut.
31
2. Struktur Data
a. Array
Array adalah tipe data terstruktur yang mempunyai komponen dalam
jumlah yang tetap dan setiap komponen dalam array dinyatakan sebagai
nomor index. Bentuk umum dari deklarasi array adalah :
Dim nama_array(tipe_index) As tipe data
dengan nama_array : nama tipe data
tipe_index : tipe data untuk nomor index
tipe data : tipe data komponen
Parameter tipe_index menentukan banyaknya komponen array tersebut.
Sebagai contoh misalnya sebuah vektor A. Vektor tersebut mempunyai
komponen Ax, Ay, dan Az. Bila A dideklarasikan bertipe integer, misalnya,
maka ketiga komponen tentu juga akan bertipe integer. Kumpulan dari ketiga
komponen A disebut dengan array, dan masing-masing komponen disebut
elemen dari array.
Dalam sistem yang akan dibuat, array akan digunakan untuk
menampung data titik, garis, bobot, garis yang telah dikunjungi selama proses
perhitungan, dan data lain yang berukuran besar.
Contoh penggunaan array satu dimensi dalam program Simulasi MST:
Private Edges(1000) As tEdge
Array Edges mempunyai indeks 0 – 999, berfungsi untuk menampung
data edge / garis. Array Edges ini bertipe data tEdge, yaitu class yang
mencakup properti edge / garis. Properti garis meliputi titik awal dan titik
akhir dari sebuah garis, dan bobotnya. Karena dalam array ini menampung
32
garis yang terdiri dari titik awal dan titik akhir, maka secara otomatis array ini
juga menampung seluruh titik yang telah diinputkan.
Aturan dalam menggunakan array adalah bahwa kita harus
mendefenisikan array dengan dimensi yang cukup besar sehingga mampu
menampung elemen-elemen array yang bersangkutan dari dalam program.
Bila pada suatu saat program yang sama akan dipakai untuk bekerja dengan
array yang dimensinya lebih besar maka kita harus mengadakan perubahan
pada indeksnya. Dalam VB .Net kita dapat menggunakan arrayList, yaitu
array satu dimensi yang dinamis, dapat menambah indeks array secara
otomatis, sesuai dengan yang dibutuhkan.
Contoh penggunaan ArrayList dalam program simulasi MST :
Private visitedEdge As ArrayList
Array visitedEdge bertipe data ArrayList adalah array yang berfungsi
untuk menampung data edge / garis yang telah dikunjungi selama proses
perhitungan pencarian minimum spanning tree. Array ini dapat menambah
indeks secara otomatis jika garis yang dikunjungi bertambah.
b. Class
Class adalah tipe data yang didalamnya dapat berisi kumpulan berbagai
tipe variabel maupun method.
Dalam sistem yang akan dibuat class akan digunakan untuk
mengelompokkan data-data yang perlu dikelompokkan sesuai dengan yang
dibutuhkan oleh sistem.
33
Contoh penggunaan class dalam program simulasi MST adalah sebagai
berikut :
Public Class tEdge
Public Vertex1 As tVertex
Public Vertex2 As tVertex
Public Bobot As Integer
Public Sub New()
Vertex1 = New tVertex
Vertex2 = New tVertex
End Sub
End Class
Class tEdge diatas adalah class garis yang berisi data-data (property)
yang dimiliki garis. Garis terbentuk dari dua titik yaitu titik asal dan titik
terminal, maka class ini menyimpan data Vertex1 sebagai titik asal dan
Vertex2 sebagai titik terminal, dimana Vertex1 dan Vertex2 bertipe data
tVertex. tVertex adalah class yang menyimpan data-data (property) titik.
c. Method DrawLine
Method DrawLine adalah method dalam VB .Net yang dapat digunakan
untuk menggambar garis untuk menghubungkan dua titik.
Contoh penggunaan method DrawLine dalam program Simulasi MST
dengan Algoritma Kruskal adalah sebagai berikut :
Dim kuas As SolidBrush = New SolidBrush(Color.Red)
Dim p1 As Pen = New Pen(kuas)
34
g.DrawLine(p1,edge.Vertex1.X,edge.Vertex1.Y,edge.Vertex2.X
, edge.Vertex2.Y)
edge.Vertex1.X,edge.Vertex1.Y,edge.Vertex2.X,
edge.Vertex2.Y adalah koordinat titik1 dan titik2. Garis yang yang
menghubungkan titik1 dan titik 2 akan digambar dengan style SolidBrush dan
dengan warna merah.
3. Algorima dan Flowchart
a. Flowchart Algoritma Kruskal
∈
Gambar 3.1 Flowchart algoritma Kruskal
35
b. Flowchart Algoritma Sistem
Gambar 3.2 Flowchart sistem Simulasi MST dengan algoritma Kruskal
36
C. Perancangan Antarmuka
Rancangan antarmuka merupakan rancangan bentuk tampilan pada layar
monitor untuk mengmplemetasikan aplikasi Simulasi Minimum Spanning Tree
dengan Algoritma Kruskal. Perancangan antarmuka digunakan untuk memberikan
gambaran tentang sistem yang akan dibuat sehingga pengguna mudah berinteraksi
dengan sistem. Antarmuka ini yang nantinya akan berinteraksi secara langsung
dengan pengguna. Oleh karena itu, menu-menu dan antarmuka dirancang agar
dapat memenuhi kebutuhan dan memudahkan pengguna dalam menggunakan
aplikasi yang akan dibuat.
Menu – menu yang disediakan pada toolbar adalah :
i. Menu File, terdiri dari tiga sub menu, yaitu :
− Menu New, digunakan untuk membuat lembar kerja baru.
− Menu Save, digunakan untuk menyimpan data yang telah
diinputkan.
− Menu Open, digunakan untuk membuka data yang sudah ada atau
sudah disimpan sebelumnya.
− Menu Exit, digunakan untuk keluar dari program.
ii. Menu About, merupakan menu yang berisi informasi release program
dan penyusun program
37
Berikut adalah rancangan struktur menu yang digunakan :
Gambar 3.3 Rancangan Struktur Menu
1. Tampilan Awal
Tampilan awal berupa form start up untuk masuk ke menu utama. Form
start up merupakan form yang akan muncul hanya beberapa waktu saja dan secara
otomatis menutup sesuai dengan kontrol waktu yang telah ditentukan. Atau biasa
disebut dengan form splash screen.
Gambar 3.4 Rancangan tampilan menu startup
38
2. Tampilan Utama
Gambar berikut adalah merupakan rancangan tampilan utama dimana
pengguna akan berinteraksi dengan program pada tampilan utama ini. Pada
tampilan ini terdapat menu – menu utama dan sub menu-nya
File About
NewOpen
Exit
Save
About
Gambar 3.5 Rancangan tampilan utama
3. Tampilan Menu Form Input dan Hasil
Untuk membuat lembar kerja baru, dapat dilakukan dengan memilih menu
New, maka akan tampil form input seperti pada gambar 3.6.
39
Gambar 3.6 Rancangan Form Input dan Hasil
Setelah jumlah titik dan rusuk diinputkan, maka akan ditampilkan sebuah
tabel atau grid, yang akan digunakan untuk menginputkan dua titik yang saling
berhubungan sehingga membentuk sebuah rusuk beserta bobotnya. Dimana
jumlah baris yang ditampilkan pada tabel ini sesuai dengan jumlah rusuk yang
telah diinputkan sebelumnya.
Jika seluruh kolom dan baris yang mewakili rusuk dan bobot pada form ini
telah diisi, maka program dapat dieksekusi dengan memilih tombol Ok. Dan
untuk mengosongkan tabel input dengan memilih tombol Reset.
Setelah klik tombol Ok, maka program akan menampilkan beberapa
informasi. Yaitu tabel hasil sorting secara ascending, tabel MST yang berisi data
hasil pencarian MST, dan gambar graf. Program juga dapat menampilkan proses
atau tahap-tahap pencarian graf MST.
40
4. Perancangan Penyimpanan
Data yang diinputkan pengguna dapat disimpan (menu save) sehingga
dapat digunakan lagi (menu open). Data yang akan disimpan adalah data tentang
jumlah titik, rusuk, dan bobot. Data ini akan disimpan pada file berekstensi .ina.
BAB IV
IMPLEMENTASI DAN PEMBAHASAN
A. Implementasi Program
1. Algoritma Kruskal
Program ini menggunakan algoritma Kruskal untuk menghitung bobot
terpendek antar titik. Selama proses pencarian MST, titik, rusuk, dan bobot yang
menjadi bagian dari MST ditampung dalam array GrafMST. Berikut adalah
penggalan programnya :
graphMst = New tGraf() For i As Integer = 0 To Graph1.JumlahSisi - 1 If Not graphMst.CekLingkar(Graph1.Edge(i)) Then graphMst.AddEdge(Graph1.Edge(i)) End If
Next
Pada penggalan program diatas, program melakukan looping, dimana
dalam looping tersebut program memanggil fungsi CekLingkar untuk
mengecek apakah rusuk yang sedang di hitung menimbulkan cycle pada array
graphMst atau tidak. Jika rusuk tidak menimbulkan cycle, maka rusuk akan
ditambahkan pada array graphMst. Program melakukan looping sebanyak
jumlah rusuk graf yang telah diinputkan pengguna.
Array graphMst adalah array yang berfungsi untuk menampung hasil
perhitungan pencarian MST. graphMst bertipe data tGraf, dimana tGraf
adalah tipe data yang berisikan kumpulan titik dan garis, yang membentuk
sebuah graf.
42
Public Class tGraf Private Edges(1000) As tEdge Private visitedEdge As ArrayList
Private endPoint As Char
End Class
Fungsi CekLingkar pada program berfungsi untuk menentukan
StartPoint dan EndPoint pada awal proses penghitungan MST. StartPoint dan
EndPoint adalah titik-titik yang akan digunakan untuk menentukan apakah
rusuk yang dihitung menimbulkan cycle pada graf MST atau tidak. Fungsi
CekLingkar juga memanggil fungsi IsCycle.
Public Function CekLingkar(ByVal e As tEdge) As Boolean endPoint = e.Vertex2.Name visitedEdge = New ArrayList() visitedEdge.Add(e) Return IsCycle(e, e.Vertex1.Name)
End Function
Fungsi IsCycle adalah fungsi yang berisi algoritma untuk menentukan
StartPoint dan EndPoint selama proses penghitungan MST. Jadi dalam proses
pencarian MST, pada setiap rusuk dengan bobot terkecil yang telah dipilih,
program melakukan looping sebanyak jumlah rusuk untuk melakukan cek cycle.
Cek cycle dilakukan dengan membandingkan StartPoint dan EndPoint. Jika
StartPoint = End Point maka rusuk tersebut menimbulkan cycle, dan berlaku
sebaliknya.
Adapun algoritma untuk menentukan StartPoint dan EndPoint adalah
sebagai berikut :
43
a. GrafAwal = array untuk menyimpan rusuk dan bobot graf awal
GrafMST = array untuk menampung rusuk dan bobot selama proses
pencarian MST
b. Menentukan StartPoint dan EndPoint. Didapatkan dari rusuk yang
mempunyai bobot terkecil dari GrafAwal, Titik1 = StartPoint dan
Titik2 = EndPoint.
c. Melakukan cek, apakah ada vtitik lain pada graf MST yang
terhubung dengan StarPoint. Jika ada titik lain yang terhubung
dengan StartPoint, maka StartPoint diganti dengan titik tersebut.
d. Melakukan cek apakah StartPoint = EndPoint. Jika StartPoint =
EndPoint maka rusuk tersebut menimbulkan cycle, dan program
tidak akan menambahkan rusuk tersebut ke array GrafMST.
Sebaliknya jika StartPoint != EndPoint, program akan menambahkan
rusuk beserta bobotnya ke array GrafMST.
e. Begitu seterusnya, proses tersebut dilakukan hingga jumlah rusuk
pada GrafMST = jumlah titik – 1 .
Implementasi algoritma diatas dapat dilihat dalam fungsi IsCycle.
Adapun penggalan program fungsi IsCycle adalah sebagai berikut :
Private Function IsCycle(ByVal E As tEdge, ByVal StartPoint As Char) As Boolean For i As Integer = 0 To JumlahSisi - 1
If Array.IndexOf(visitedEdge.ToArray, Edges(i)) >= 0 Then Continue For
If Edges(i).Vertex1.Name = StartPoint Or Edges(i).Vertex2.Name = StartPoint Then
visitedEdge.Add(Edges(i))
44
If Edges(i).Vertex1.Name = endPoint Or Edges(i).Vertex2.Name = endPoint Then
Return True End If Dim SP As Char If Edges(i).Vertex1.Name = StartPoint Then SP = Edges(i).Vertex2.Name ElseIf Edges(i).Vertex2.Name = StartPoint Then SP = Edges(i).Vertex1.Name End If If IsCycle(Edges(i), SP) Then Return True End If Next Return False
End Function
2. Proses Penyimpanan Data Verteks
Untuk memudahkan pengguna, data yang dimasukkan dapat disimpan
dalam file berekstensi .ina . File ini akan menyimpan data-data berupa :
a. Titik 1 (titik awal)
b. Titk 2 (titik akhir), titik 1 dan titik 2 akan membentuk sebuah rusuk.
c. Bobot
Pada prosedur sub SaveMenu_Click, semua data pada tabel input akan
diubah terlebih dahulu ke variabel bertipe data string. Antara data Titik1, Titik2,
dan Bobot dipisahkan dengan karakter spasi.
Private Sub SaveMenu_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles SaveMenu.Click Dim dlg As SaveFileDialog = New SaveFileDialog() dlg.Filter = ".ina|*.ina" If dlg.ShowDialog() = Windows.Forms.DialogResult.Cancel Then Return If File.Exists(dlg.FileName) Then File.Delete(dlg.FileName) grid.EndEdit() Using sw As StreamWriter = New StreamWriter(dlg.FileName)
45
sw.WriteLine(".ina file") For Each row As DataGridViewRow In grid.Rows For Each cell As DataGridViewCell In row.Cells sw.Write(cell.Value.ToString & " ") Next sw.WriteLine() Next sw.Close() End Using End Sub
3. Proses Open Data Verteks
Untuk membuka data verteks yang telah disimpan oleh pengguna, data-
data yang telah diubah ke dalam variabel bertipe data string harus dipilah-pilah
dahulu. Salah satu fungsi yang dapat digunakan untuk memilah data adalah
fungsi split. Fungsi ini mengembalikan data berupa array berdasarkan karakter
pembatas.
Private Sub menuOpen_Click(ByVal sender As System.Object, ByVal e As System.EventArgs) Handles menuOpen.Click Dim dlg As OpenFileDialog = New OpenFileDialog() dlg.Filter = ".ina|*.ina" If dlg.ShowDialog() = Windows.Forms.DialogResult.Cancel Then Exit Sub End If Dim frm As New InputBobotForm() frm.MdiParent = Me frm.Show() Using sr As StreamReader = New StreamReader(dlg.FileName) If Not sr.ReadLine() = ".ina file" Then MessageBox.Show("File tidak valid ! ") Exit Sub End If Dim line As String Do line = sr.ReadLine() If String.IsNullOrEmpty(line) Then Exit Do End If
46
Dim RowIndex As Integer = frm.grid.Rows.Add() Dim splitter() As Char = {" "} Dim data() As String = line.Split(splitter) frm.grid(0, RowIndex).Value = data(0) frm.grid(1, RowIndex).Value = data(1) frm.grid(2, RowIndex).Value = data(2) frm.grid(3, RowIndex).Value = data(3) Loop Until line Is Nothing sr.Close() End Using End Sub
4. Proses gambar graf
Untuk menggambar graf awal, nama titik, relasi antar titik, dan bobot
yang digunakan diambil dari array graph, yaitu array yang berisi kumpulan titik,
rusuk, dan bobot graf awal.
Dalam bahasa pemrograman VB .Net terdapat beberapa method atau
class yang dapat digunakan untuk menggambar objek. Untuk menggambar garis
atau rusuk menggunakan class DrawLine, dan untuk melampirkan nama titik
dan bobot, menggunakan class DrawString.
Private Sub DrawGraph(ByVal Graph As tGraf) g = Panel1.CreateGraphics() g.Clear(Color.White) buatKoordinat(Graph) ' Dim myfont As New Font("Arial", 12) Dim kuas As SolidBrush = New SolidBrush(Color.Black) For i As Integer = 0 To Graph.JumlahSisi - 1 Dim edge As tEdge = Graph.Edge(i) For j As Integer = 0 To Graph.JumlahTitik - 1 If edge.Vertex1.Name = titik(j).Name Then edge.Vertex1 = titik(j) End If Next For j As Integer = 0 To Graph.JumlahTitik - 1 If edge.Vertex2.Name = titik(j).Name Then edge.Vertex2 = titik(j) End If Next
47
g.DrawString(edge.Vertex1.Name, myfont, kuas, edge.Vertex1.X, edge.Vertex1.Y) g.DrawString(edge.Vertex2.Name, myfont, kuas, edge.Vertex2.X, edge.Vertex2.Y) Dim p1 As Pen = New Pen(kuas) g.DrawLine(p1, edge.Vertex1.X, edge.Vertex1.Y, edge.Vertex2.X, edge.Vertex2.Y) g.DrawString(edge.Bobot, myfont, kuas, edge.Vertex1.X + ((edge.Vertex2.X - edge.Vertex1.X) / 2), edge.Vertex1.Y + ((edge.Vertex2.Y - edge.Vertex1.Y) / 2)) Next End Sub
Untuk menggambar graf hasil pencarian MST, nama titik, relasi antar
titik, dan bobot yang digunakan diambil dari array graphMst, yaitu array yang
berisi kumpulan titik, rusuk, dan bobot graf MST yang telah terbentuk.
Private Sub DrawGraphMst()
g = Panel1.CreateGraphics() Dim myfont As New Font("Arial", 12) Dim kuas As SolidBrush = New SolidBrush(Color.Red) titik = GraphAwal.getTitik Dim edge As tEdge = graphMst.Edge(itr) For j As Integer = 0 To titik.Count - 1 If edge.Vertex1.Name = titik(j).Name Then edge.Vertex1 = titik(j) Exit For End If Next For j As Integer = 0 To titik.Count - 1 If edge.Vertex2.Name = titik(j).Name Then edge.Vertex2 = titik(j) Exit For End If Next g.DrawString(edge.Vertex1.Name, myfont, kuas, edge.Vertex1.X, edge.Vertex1.Y)
48
g.DrawString(edge.Vertex2.Name, myfont, kuas, edge.Vertex2.X, edge.Vertex2.Y) Dim p1 As Pen = New Pen(kuas) g.DrawLine(p1, edge.Vertex1.X, edge.Vertex1.Y, edge.Vertex2.X, edge.Vertex2.Y) itr += 1 End Sub
B. Implementasi Antarmuka
1. Tampilan Awal
Tampilan awal berupa form start up untuk masuk ke menu utama. Form
start up merupakan form yang akan muncul hanya beberapa waktu saja dan
secara otomatis menutup sesuai dengan kontrol waktu yang telah ditentukan.
Form ini biasa disebut form splash screen.
Gambar 4.1 Tampilan awal
2. Tampilan Utama
Tampilan utama merupakan antarmuka induk yang berisi menu pilihan
untuk menuju ke menu yang lain. Secara umum menu utama program Simulasi
MST dengan Algoritma Kruskal adalah sebagai berikut :
49
a. Menu File
Berisi empat sub menu, yaitu :
Menu New
Menu ini berfungsi untuk memanggil lembar kerja baru pengguna
akan diminta untuk menginputkan jumlah titik dan jumlah rusuk.
Menu Open
Menu ini berfungsi untuk membuka data yang sudah ada atau
disimpan sebelumnya.
Menu Save
Menu ini berfungsi untuk menyimpan data yangtelah diinputkan.
Menu Exit
Menu ini berfungsi untuk keluar dari program.
b. Menu About
Menu About adalah menu untuk menampilkan informasi tentang
penyusun program.
50
Gambar 4.2 Tampilan Utama
3. Tampilan Form Input dan Hasil
Gambar 4.3 Form Input dan Hasil
Form ini merupakan antarmuka yang digunakan untuk melakukan input
data, proses, sekaligus menampilkan hasil dari pencarian MST. Pertama-tama
pengguna diminta memasukkan jumlah titik dan jumlah rusuk, kemudian akan
51
ditampilkan grid atau tabel, dimana jumlah baris atau row dari tabel ini sesuai
dengan jumlah rusuk yang dimasukkan oleh pengguna. Melalui tabel ini
pengguna dapat memasukkan data titik dan bobot dari graf yang akan dicari
MST nya.
Untuk melakukan penghitungan atau pencarian MST, pengguna dapat
memilih tombol Ok. Maka program akan menampilkan tabel hasil sorting
(ascending), tabel hasil pencarian MST, gambar graf, dan jumlah bobot
minimum MST.
Tabel hasil sorting menampilkan data titik dan bobot yang telah
diurutkan secara ascending, yaitu beruruan dari bobot yang paling kecil ke
bobot yang paling besar.
Tabel hasil pencarian MST, menampilkan hasil pencarian MST yang
meliputi data titik, rusuk dan bobot. Data ditampilkan secara berurutan sesuai
dengan proses pembentukan MST, yaitu rusuk yang mempunyai bobot paling
kecil ke bobot yang paling besar, dengan ketentuan rusuk tersebut tidak
menimbulkan cycle.
Gambar graf yang tampilkan program merupakan gambar graf awal,
untuk menampilkan gambar graf MST, pengguna dapat memilih tombol
GrafMST, kemudian untuk menampilkan gambar tahap-tahap proses
pembentukan MST, gambar graf harus direset terlebih dahulu dengan memilih
tombol Reset, setelah itu pilih tombol Berikutnya, maka akan ditampilkan proses
pembentukan graf MST secara bertahap. Proses pembentukan MST secara
bertahap dilakukan dengan pemilihan rusuk yang mempunyai bobot terkecil,
52
yang ditandai dengan warna merah. Untuk menampilkan kembali graf awal,
pengguna dapat memilih tombol Reset.
4. Tampilan Open
Pengguna juga dapat membuka data yang sudah pernah diinputkan
sebelumnya dengan memilih menu open.
Gambar 4.4 Tampilan Open
5. Tampilan Save
Pengguna dapat menyimpan data titik, rusuk, dan bobot yang telah
diinputkan dengan memilih menu Save. Data akan disimpan dengan ekstensi
.ina.
53
Gambar 4.5 Tampilan Save
C. Pembahasan
Program Simulasi Minimum Spanning Tree menggunakan algoritma
kruskal. Jumlah titik maksimal yang dapat diinputkan adalah sebanyak 12 titik.
1. Contoh Penyelesaian Masalah MST
Untuk mengetahui cara kerja program Simulasi MST dengan algoritma
Kruskal ini, program akan diujicobakan pada data 7 titik dan 11 rusuk, dengan
detail data pada tabel 3.1.
Program akan mengurutkan data bobot secara ascending, yaitu dari
bobot yang terkecil ke bobot yang terbesar. Data diurutkan berdasarkan bobot
terkecil untuk mempermudah proses pencarian MST karena program akan
mengambil bobot yang terkecil terlebih dahulu, selama rusuk dengan bobot
terkecil tersebut tidak menimbulkan cycle dalam graf. Data yang telah diurutkan
berdasarkan bobot terkecil dapat dilihat pada tabel 3.2.
54
Tabel 4.1 Data ujicoba
No Rusuk Bobot
1 AB 7
2 AD 5
3 BD 9
4 BC 8
5 BE 7
6 DE 15
7 DF 6
8 EF 8
9 EG 9
10 FG 11
11 CE 5
Total Bobot 90
Tabel 4.2 Data ujicoba yang telah di sorting (ascending)
No Rusuk Bobot
1 AD 5
2 CD 5
3 DF 6
4 AB 7
5 BE 7
6 BC 8
7 EF 8
8 BD 9
9 EG 9
10 FG 11
11 DE 15
Total Bobot 90
55
Setelah data diurutkan berdasarkan bobot terkecil, kemudian program
melakukan pencarian MST, dimulai dengan bobot terkecil. Pada data diatas,
bobot terkecil adalah lima, dan ada dua rusuk yang mempunyai bobot lima. Jika
terdapat lebih dari satu rusuk yang mempunyai bobot terkecil sama, maka
program akan memilih secara acak rusuk yang akan dihitung terlebih dahulu.
Setelah itu program akan melakukan cek cycle, apakah rusuk tersebut
menimbulkan cycle pada graf MST atau tidak. Jika rusuk menimbulkan cycle,
maka rusuk beserta bobot tidak ditambahkan pada graf MST. Program akan
menentukan bobot terkecil berikutnya, melakukan cek cycle, dan menambahkan
rusuk dan bobot ke dalam graf MST, begitu seterusnya hingga jumlah rusuk graf
MST = jumlah titik graf - 1 .
Berikut adalah gambar graf selama proses pencarian MST. Garis yang
berwarna merah adalah rusuk-rusuk yang membentuk MST.
56
Gambar 4.6 Proses pertahap pembentukan graf MST
57
Sehingga didapatkan hasil pencarian MST dalam tabel berikut :
Tabel 4.3 Hasil pencarian MST untuk data ujicoba
No Rusuk Bobot
1 AD 5
2 CE 5
3 DF 6
4 AB 7
5 BE 7
6 EG 9
Total Bobot 39
Rusuk yang yang membentuk MST adalah AD – CE – DF – AB – BE –
EG, dengan total bobot adalah 39.
D. Analisa
Algoritma Kruskal hanya dapat diterapkan pada graf tidak berarah,
karena algoritma ini tidak menghitung atau memperdulikan arah antar titik dan
hanya memperhitungkan bobot dalam melakukan pengurutan untuk melakukan
pencarian bobot terpendek dari masing-masing titik / vertex.
1. Kelebihan Program
Dari program pencarian jalur terpendek ini, kelebihan-kelebihan yang
didapat adalah :
a. Hasil yang diperoleh ditampilkan dalam bentuk visualisasi graf,
memudahkan user dalam membaca hasil perhitungan dan memahami
cara kerja algoritma Kruskal.
58
b. Data titik, rusuk dan bobot dapat disimpan, sehingga datanya dapat
di-update oleh user.
2. Kekurangan Program
Jumlah titik masih dibatasi sebanyak dua belas titik.
BAB V
PENUTUP
Bagian akhir dari penulisan skripsi ini ditulis beberapa kesimpulan dan
saran sehubungan dengan hal-hal yang terkait dengan pencarian jalur terpendek
dari bab-bab sebelumnya.
A. Kesimpulan
Kesimpulan yang diambil dari pembuatan aplikasi Simulasi Minimum
Spanning Tree menggunakan algoritma Kruskal adalah :
1. Pencarian MST dengan menggunakan algoritma Kruskal hanya dapat
dilakukan pada graf tak berarah.
2. Algoritma Kruskal dapat diimplementasikan ke pemrograman komputer
menggunakan developer Visual Basic.Net.
3. Untuk mengimplementasikan graf ke program komputer digunakan
matriks dua dimensi dalam menampung datanya.
B. Saran
Saran yang dapat dipertimbangkan untuk pengembangan program ini adalah
sebagai berikut :
1. Program Simulasi Minimum Spanning Tree dengan Algoritma Kruskal
merupakan program simulasi untuk mempermudah pemahaman pencarian
MST, maka visualisasi graf berperan penting dalam program ini. Akan
tetapi algoritma untuk menampilkan gambar graf yang telah dibuat dalam
program ini belum fleksibel. Penulis menyarankan jika ada yang ingin
60
mengembangkan program ini dapat membuat algoritma untuk
menggambar graf yang lebih optimal dan fleksibel sehingga penyajian
gambar graf akan lebih baik.
61
DAFTAR PUSTAKA
Arzinal, D., 2006, Membangun Pohon Merentang Minimum Dari Algoritma Prim
dengan Strategi Greedy, Institut Teknologi Bandung, Bandung.
Eep, S S., 1990, Discrete Mathematics with Applications, Wadsworth Publishing Co,
California.
Lovasz, L., Pelikan, J., Vesztergombi, K., 2003, Discrete Mathematics Elementary
and Beyond, Springer, New York.
Munir, R., 2001, Matematika Diskrit, Penerbit Informatika, Bandung.
Muntaha, A., 2006, Graf Pohon dan Implementasinya Dalam Beberapa Persoalan,
Institut Teknologi Bandung, Bandung.
Ramadiyan, D., 2006, Aplikasi Representasi Graf, Institut Teknologi Bandung,
Bandung.
Siang, J J., 2004, Matematika Diskrit dan Aplikasinya pada Ilmu Komputer, Andi,
Yogyakarta.
www.informatika.org/~rinaldi/Matdis/2006-2007/Makalah-2006.htm (diakses pada
tanggal 21 Juni 2007)