i
MENENTUKAN MINIMUM SPANNING TREE MENGGUNAKAN ALGORITMA KRUSKAL DENGAN BAHASA PEMROGRAMAN C
TUGAS AKHIR
ASDITA RIZKI LUBIS 112406125
PROGRAM STUDI D3 TEKNIK INFORMATIKA DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
ii
MENENTUKAN MINIMUM SPANNING TREE MENGGUNAKAN ALGORITMA KRUSKAL DENGAN BAHASA PEMROGRAMAN C
TUGAS AKHIR
Diajukan untuk melengkapi tugas dan memenuhi syarat memperoleh Ahli Madya
ASDITA RIZKI LUBIS 112406125
PROGRAM STUDI D3 TEKNIK INFORMATIKA DEPARTEMEN MATEMATIKA FAKULTAS MATEMATIKA DAN ILMU PENGETAHUAN ALAM UNIVERSITAS SUMATERA UTARA MEDAN 2014
Universitas Sumatera Utara
i
PERSETUJUAN
Judul
: Menentukan Minimum Spannning Tree Menggunakan Algoritma Kruskal Dengan Bahasa Pemrograman C
Kategori
: Tugas Akhir
Nama
: Asdita Rizki Lubis
Nomor Induk Mahasiswa
: 112406125
Program Studi
: D3 TEKNIK INFORMATIKA
Departemen
: Matematika
Fakultas
: Matematika Dan Ilmu Pengetahuan Alam Universitas Sumatera Utara
Disetujui di Medan, Juni 2014
Disetujui oleh: Program Studi D3 Teknik Informatika FMIPA USU Ketua,
Dr. Elly Rosmaini, M.Si NIP. 19600520 198503 2 002
Pembimbing
Dr. Mardiningsih, MSi NIP. 19630405 198811 2 001
Universitas Sumatera Utara
ii
PERNYATAAN
MENENTUKAN MINIMUM SPANNING TREE MENGGUNAKAN ALGORITMA KRUSKAL DENGAN BAHASA PEMROGRAMAN C
TUGAS AKHIR
Saya mengakui bahwa tugas akhir ini adalah hasil kerja saya sendiri, kecuali beberapa kutipan dan ringkasan yang masing-masing disebutkan sumbernya.
Medan, Juni 2014
ASDITA RIZKI LUBIS 112406125
Universitas Sumatera Utara
iii
PENGHARGAAN
Alhamdulillah, puji dan syukur penulis panjatkan kepada Allah SWT yang Maha Pemurah dan Penyayang, dengan limpahan rahmat dan hidayah-Nya Penulis dapat menyelesaikan penyusunan tugas akhir ini dengan judul Menentukan Minimum Spanning Tree menggunakan Algoritma Kruskal Dengan Bahasa Pemrograman C.
Ucapan terima kasih penulis sampaikan kepada Ibu Dr. Mardiningsih, MSi, selaku pembimbing sekaligus Sekertaris Departemen Matematika FMIPA USU, yang telah memberikan panduan dan bimbingan dalam merampungkan tugas akhir ini. Ucapan terima kasih juga ditujukan kepada Ketua Departemen Matematika FMIPA USU Bapak Prof.Drs. Tulus, M.Si, Ibu Dr. Elly Rosmaini, MSi selaku Ketua Prodi D3 Teknik Informatika, Bapak Syahriol Sitorus S.Si, M.IT selaku Sekretaris Prodi D3 Teknik Informatika, Dekan, Pembantu Dekan FMIPA USU, serta segenap dosen dan pegawai Fakultas Matematika dan Ilmu Pengetahuan Alam Universitas Sumatera Utara, serta rekan-rekan mahasiswa D3 Teknik Informatika Universitas Sumatera Utara. Tak lupa penulis juga mengucapkan banyak terima kasih kepada orangtua tercinta yang telah memberikan kasih sayang, kekuatan dan doa kepada penulis serta sanak saudara yang telah memberikan banyak dukungan dan doa dalam menyelesaikan pendidikan D3 Teknik Informatika Universitas Sumatera Utara. Semoga Allah akan membalasnya.
Universitas Sumatera Utara
iv
ABSTRAK
Jika semua jaringan listrik dibuat terlalu banyak maka biaya akan boros. Beberapa jalur yang menghubungkan 2 kota secara langsung tidak perlu dibuat karena kotakota tersebut tetap dapat teraliri listrik secara tidak langsung, yaitu dengan melalui kota lain sedemikian hingga total biaya pemasangan jaringan listrik seminimum mungkin. Atau dengan kata lain, mencari pohon rentang dengan total bobot terkecil. Melihat hal itu penulis ingin membantu user menemukan pohon rentang minimum secara sederhana menggunakan Algoritma Kruskal dengan Bahasa Pemrograman C. Aplikasi ini berguna untuk mencari pohon rentang dengan total bobot seminimum mungkin atau disebut pohon merentang minimum.
Universitas Sumatera Utara
v
ABSTRACT
If all the electricity grid made too much of the costs wiil be wasteful. Multiple paths that connect the two cities directly not need to be made because the cities will still be powered indirectly, with another city such that the total cost of the installation of the electrical grid to a minimum. Or in other words finding a spanning tree with total weight of the smallest. See it author wants to help user find the minimum spanning tree using Kruskal algorithm with a simple programming language C. This application is useful to find a spanning tree with minimum total weight or the so called minimum spanning tree.
Universitas Sumatera Utara
vi
DAFTAR ISI
Halaman i ii iii iv v vi
Persetujuan Pernyataan Penghargaan Abstrak Abstract Daftar Isi Daftar Tabel Daftar Gambar
viii ix
Bab 1. Pendahuluan 1.1. Latar Belakang Rumusan Masalah 1.2. 1.3. Batasan Masalah 1.4. Tujuan 1.5. Manfaat 1.6. Metodologi Penelitian Sistematika Penulisan 1.7.
1 1 2 3 3 3 4 5
Bab 2. Landasan Teori 2.1. Pengertian Algoritma 2.2. Sejarah Graf 2.3. Teori Graf 2.3.1. Graph Sederhana(Simple Graph) 2.3.2. Graf Tak-Berarah (Undirected Graph)
7 7 8 8 9 9
2.4. 2.5. 2.6. 2.7. 2.8. 2.9. 2.10. 2.11. 2.12. 2.13. 2.14
2.15
2.3.3. Graf Berbobot Pohon(Tree) Pohon Merentang Graf Berlabel Pohon Merentang Minimum Aplikasi Minimum Spanning Tree Algoritma Kruskal Algoritma Prim Pengertian Komputer Sejarah Singkat C Mengenal Pemrograman Pembahasan Bahasa Pemrograman C 2.14.1 Identifier, Keywords dan Tipe Data Pada Bahasa C 2.14.2 Escape Character pada Bahasa C Dev C++
Bab 3 Perancangan Sistem 3.1. Perancangan Sistem
10 10 11 12 13 14 15 18 18 19 19 20 23 25 26 32 32
Universitas Sumatera Utara
vii
3.2. 3.3. 3.4.
3.5 3.6
3.7 3.8
3.9
Pemodelan Aplikasi Flowchart Struktur Kontrol Percabangan 3.4.1. Pola IF 3.4.2. Bentuk IF ELSE Struktur Kontrol Perulangan 3.5.1. Struktur For() Fungsi Main 3.6.1. int main() 3.6.2. void main() Pointer Array 3.8.1. Array 1 Dimensi 3.8.2. Array 2 Dimensi Perancangan Tampilan 3.9.1. Menu utama 3.9.2. Compile dan Run 3.9.3. Command Prompt
32 34 36 37 37 38 39 40 40 40 41 41 42 42 44 44 44 45
Bab 4 Impementasi Sistem 4.1. Pengertian Implementasi Sistem Tujuan Implementasi Sistem 4.2. 4.3. Kebutuhan Sistem 4.3.1. Perangkat Keras (Hardware) 4.3.2. Perangkat Lunak (Software) 4.3.3. Brainware 4.4. Tampilan Akhir Program 4.5. Cara Kerja Program
46 46 47 47 47 48 48 49 50
Bab 5 Penutup 5.1. Kesimpulan 5.2. Saran
52 52 53
Daftar Pustaka Lampiran
54
Universitas Sumatera Utara
viii
DAFTAR TABEL
No tabel 2.1
Judul
Halaman
Tabel pembentukan pohon merentang minimum dengan algoritma Kruskal
17
2.2
Tabel contoh statement
22
2.3
Keywords pada C
23
2.4
Ukuran tipe data bilangan bulat
24
2.5
Tipe Data Bilangan Pecahan
24
2.6
Tipe Data Non-Numerik
25
2.7
Tipe Karakter Khusus
26
3.1
Simbol-simbol Flowchart
34
Universitas Sumatera Utara
ix
DAFTAR GAMBAR
No Gambar
Judul
Halaman
2.1
Graf lengkap G dan empat buah pohon
11
2.2
Graf Jaringan Jalur Rel Kereta Api
14
2.3
Struktur Program C
22
2.4
Tampilan Awal Dev C++
27
2.5
Tampilan Membuat Project Baru
28
2.6
Cara Menyimpan Program
29
2.7
Jendela Area Kerja Dev C++
30
3.1
Diagram Alir Perancangan
33
3.2
Flowchart Pola IF
37
3.3
Flowchart Bentuk IF ELSE
38
3.4
Flowchart Struktur For()
39
3.5
Flowchart Program
43
3.6
Kerangka Tampilan Halaman Program
44
4.1
Tampilan Akhir Program
49
4.2
Graph Berlabel
50
4.3
Tampilan Awal Masukkan Verteks
50
4.4
Input Matriks Adjasensi
51
4.5
Total Biaya Minimum
51
4.6
Hasil Minimum Spanning Tree
52
Universitas Sumatera Utara
