1 BAB I PENDAHULUAN 1.1 Latar Belakang Masalah Graf adalah suatu himpunan simpul yang dihubungkan dengan busurbusur. Pada sebuah graf hubungan antar s...
1.1 Latar Belakang Masalah Graf adalah suatu himpunan simpul yang dihubungkan dengan busur-
W
busur. Pada sebuah graf hubungan antar simpul yang dihubungkan oleh busur memiliki sebuah keterkaitan. Graf dilihat dari jenisnya ada beberapa, salah satu
KD
diantaranya yaitu graf sederhana tidak berarah dan tidak berbobot serta dilihat dari hubungannya merupakan graf terhubung. Pada penerapannya dalam beberapa kasus, graf digunakan sebagai representasi dari suatu permasalahan. Oleh karena
U
itu jika terdapat beberapa graf yang identik atau isomorfis maka dapat dikatakan permasalahan yang direpresentasikan oleh graf tersebut memiliki penyelesaian
IK
yang sama. Proses penelusuran dilakukan untuk menemukan pohon bentangan minimum pada sebuah graf.
M IL
Penelusuran graf ada 2 yaitu Breadth First Search (BFS) dan Depth First Search (DFS). Kedua metode penelusuran tersebut memiliki cara penelusuran yang berbeda sehingga dalam pembentukan pohon bentangan minimum graf juga akan berbeda, meskipun tidak menutup kemungkinan akan terbentuk pohon bentangan minimum yang sama pada suatu graf. Dalam malakukan penelusuran program membutuhkan algoritma yang berfungsi memberikan urutan langkah penyelesaian penelusuran. Algoritma yang dapat digunakan diantaranya algoritma non-rekursif dan rekursif. Untuk mengetahui proses dan penggunaan masing-masing algoritma secara jelas, maka pada penulisan tugas akhir ini akan membahas mengenai penggunaan algoritma rekursif dan non-rekursif dalam penelusuran sebuah graf dengan menggunakan metode penelusuran DFS dan BFS.
1
1.2 Perumusan Masalah Pemaparan pada latar belakang masalah di atas telah dibahas mengenai pemikiran dasar penulisan ini. Oleh karena itu pada sub bab ini akan disajikan mengenai beberapa rumusan masalah yang dibahas pada penulisan ini, adapun permasalahan yang akan dibahas pada penulisan ini sebagai berikut : 1. Bagaimana cara penelusuran metode DFS dan BFS dengan menggunakan algoritma non-rekursif maupun algoritma rekursif pada sebuah graf? 2. Bagaimana perbedaan perkiraan lama waktu penelusuran antara metode DFS dan BFS dengan menggunakan algoritma rekursif dan non-rekursif
W
pada sebuah graf?
KD
1.3 Batasan Masalah
Adapun batasan masalah yang terdapat dalam penulisan ini antara lain: 1. Graf yang digunakan adalah jenis graf sederhana tidak berbobot dan
U
tidak berarah.
2. Jumlah node yang akan dijadikan sampel percobaan penelusuran yaitu 20, 40, 60, 80, 100.
IK
3. Pemberian jumlah egdes minimal membentuk graf terhubung dan jumlah maksimum egdes membentuk graf komplit.
M IL
4. Jenis keterhubungan graf yang digunakan dalam inputan adalah jenis graf yang terhubung.
5. Pada sistem yang dibangun inputan berupa graf dalam bentuk struktur data serta penyajian output juga dalam bentuk struktur data.
6. Algoritma yang digunakan dalam penulisan tersebut menggunakan algoritma rekursif dan non-rekursif
1.4 Tujuan Penelitian Dalam penulisan ini penulis mempunyai maksud dan tujuan dalam pembuatannya. Adapun dalam tujuan penulisan tersebut penulis ingin memaparkan pemecahan masalah yang telah diuraikan pada perumusan masalah
2
di dalam penulisan. Pada subbab ini penulis akan memaparkan maksud dan tujuan dari penulisan, adapun tujuan dari penulisan tersebut antara lain: 1. Mengetahui cara penelusuran graf secara Breadth First Search (BFS) dan Depth First Search (DFS). 2. Mengetahui cara penggunaan algoritma nonrekursif dalam melakukan penelusuran dengan metode DFS dan BFS. 3. Mengetahui cara penggunaan algoritma rekursif dalam melakukan penelusuran dengan metode DFS dan BFS. 4. Mengetahui perbedaan non-rekursif dan rekursif dalam pemrosesannya pada penelusuran sebuah graf baik menggunakan metode Breadth First
W
Search (BFS) maupun dengan menggunakan metode Depth First Search (DFS).
KD
Dengan pemaparan diatas maka penulis akan sangat terbantu dalam melakukan penulisan ini. Hal tersebut dikarenakan semua pembahasan masalah
dipaparkan di atas.
U
yang ada dalam perumusan masalah akan merujuk pada tujuan-tujuan yang telah
IK
1.5 Metode atau Pendekatan Penulisan tugas akhir ini memiliki Metode atau pendekatan yang
M IL
bertujuan untuk membantu penulis dalam melakukan pembahasan permasalahan, selain itu berguna bagi pembaca untuk melihat gambaran umum langkah-langkah yang digunakan penulis dalam melakukan pembahan perumusan masalah. Adapaun metode atau pendekatan yang digunakan dalam penelitian untuk tugas akhir ini sebagai berikut:
1. Studi Pustaka Pada penyusunan penulisan dilakukan pengumpulan data pustaka yang berhubungan dengan materi yang akan dibahas. Penulis dalam mencari pustaka akan melakukan pencarian jurnal-jurnal ilmiah baik yang terdapat di internet maupun di perpustakaan. Selain itu studi pustaka akan dilakukan dengan percarian buku-buku teori tentang graf dan algoritma yang akan dibandingkan.
3
2. Implementasi Pada bagian ini penulis akan melakukan perancangan program yang bertujuan untuk menerapkan jalannya kedua algoritma tersebut. Dalam pembuatan program tersebut, penulis menerapkan teori-teori yang sudah diperoleh dalam studi pustaka sehingga dalam melakukan program ini penulis memperoleh sebuah data mengenai penelusuran graf. 3. Analisis Pada bagian ini penulis melakukan analisa dari data yang telah diperoleh
kemudian
melakukan
pembahasan
sesuai
dengan
W
permasalahan yang akan dibahas. Dalam melakukan analisis tersebut penulis memiliki acuan teori yang telah diperoleh pada saat studi
KD
pustaka. Proses analisa bertujuan untuk menemukan jawaban dari rumusan masalah yang ada.
U
1.6 Sistematika Penulisan
Pada sub bab ini penulis memaparkan struktur penulisan akan dilakukan.
IK
Hal tersebut bertujuan untuk memudahkan pembaca dalam membaca penulisan tugas akhir ini, adapun sistematika penulisan tersebut dibagi dalam beberapa bab
M IL
sebagai berikut:
• BAB I
Penulis akan memaparkan latar belakang penulisan ini, dimana
terdapat rumusan yang akan di bahas dan juga tujuan penulisan yang digunakan
sebagai
acuan
pembahasan
permasalahan.
Dalam
melakukan pembahasan penulisan penulis juga menuliskan batasan masalah yang akan di bahas sehingga mempermudah penulis dalam melakukan pembahasan. Selain itu pada bagian ini di sajikan mengenai metode atau pendekatan yang akan dilakukan serta memberikan sistematika penulisan yang berguna untuk membantu pembaca memahami struktur penulisan.
4
•
BAB II Penulis akan menyajikan tinjauan pustaka dan landasan teori yang berisi tentang berbagai teori yang didapatkan dari berbagai sumber pustaka. Tinjauan pustaka dan landasan teori memuat penjelasan tentang konsep dan prinsip utama yang diperlukan untuk memecahkan rumusan masalah. Dalam bab ini landasan teori dan tinjauan pustaka berbentuk uraian kualitatif, model sistematis, atau persamaanpersamaan yang langsung berkaitan dengan permasalahan yang akan dibahas. BAB III
W
•
Bab ini mencakup analisis teori yang digunakan dan bagaimana menterjemahkannya ke dalam program yang akan dibuat sebagai
KD
bahan analisis. Adapun pada bab ini memuat flow chart algoritma yang digunakan untuk melakukan penelusuran graf. Pada bab ini juga akan memaparkan pernancangan simulasi yang akan dibuat secara detail dan
U
lengkap. Hal tersebut bertujuan membantu penulis dalam pembuatan program tersebut, selain itu juga membantu pembaca untuk memahami •
IK
cara kerja program simulasi tersebut. BAB IV
M IL
Bab ini memuat analisis dari data yang telah diperoleh dari hasil
eksekusi program yang telah dibuat. Penulisan analisis berupa penjelasan teoritis baik secara kualitatif maupun secara kuantitatif. Dalam melakukan analisis penulis melakukan perbandingan data yang telah diperoleh kemudian melakukan pembahasan sesuai dengan toeri yang tedapat pada landasan teori.
•
BAB V Bab ini akan memuat kesimpulan yang telah dirumuskan berdasarkan hasil analisa yang telah dilakukan. Selain itu juga memuat saran yang bertujuan untuk memberikan masukan supaya dapat dikembangkan lagi.
