Algoritma Depth First Search (DFS) dan Implementasinya

Judul Jurnal: Aplikasi Berbasis Mobile untuk Pencarian Rute Angkutan Umum Kota Makassar Menggunakan Algoritma Depth First Search

Sumber Gambar: arsy.co.id

Di seluruh wilayah, sarana dan prasarana sangat diperlukan untuk mendukung aktivitas masyarakat. Salah satu contohnya ialah di Kawasan kota Makassar yang merupakan tempat kegiatan penduduk dengan segala aktivitasnya. Dilihat dari segi pergerakan penduduk, bertambahnya jumlah penduduk seiring dengan banyaknya pergerakan yang terjadi baik dari dalam maupun luar kota. Maka dari itu karena alasan tersebut, diperlukan adanya keseimbangan antara sarana dan prasarana yang mendukung seperti khususnya di bidang angkutan sebagai penunjang mobilitas penduduk. Saat ini telah dioperasikan angkutan umum sebanyak 15 rute trayek di Kota Makassar dimana semua tujuan akhir rute adalah pusat kota yang merupakan pusat kegiatan perdagangan, jasa, perkantoran dan berbagai tempat beberapa objek wisatawan. Namun timbul beberapa permasalahan yaitu para pendatang maupun wisatawan banyak yang tidak mengetahui rute trayek yang dituju angkutan sehingga mereka kesulitan untuk memilih angkutan umum mana yang harus digunakan untuk mencapai suatu tempat.

 

Maka dari itu, dibuatlah satu aplikasi yang didalamnya terdapat fasilitas pencarian kode angkutan umum yang akan ditumpangi untuk pergi ke suatu tempat. Dimana didalamnya terdapat tampilan kode angkutan umum, informasi jalur yang dilalui angkutan umum dan juga diperlihatkan jalur rute angkutan melalui Google Maps. Metode yang akan digunakan untuk menentukan jarak terdekat dari posisi pengguna aplikasi dengan beberapa pilihan rute adalah Algoritma Depth First Search. Dengan dibuatnya aplikasi ini, diharapkan calon penumpang dapat dengan mudah mencari kode angkutan umum yang ingin ditumpanginya melalui smartphone android dan juga dapat menemukan rute angkutan umum yang terdekat.

Alur Algoritma Depth First Search (DFS):

Sumber Gambar: http://cikalinspirasi.blogspot.com

 

Lebih jelasnya, Algoritma Depth First Search (DFS) adalah algoritma pencarian pada sebuah pohon dengan menelusuri satu cabang sebuah pohon sampai menemukan solusi. Algoritma ini melakukan penelusuran struktur graf/pohon berdasarkan kedalaman. Pencarian dilakukan pada satu node dalam setiap level dari yang paling kiri dan dilanjutkan pada node sebelah kanan Jika solusi ditemukan maka tidak diperlukan proses backtracking yaitu penelusuran balik untuk mendapatkan jalur yang diinginkan. Pada algoritma DFS pemakaian memori tidak banyak karena hanya node-node pada lintasan yang aktif saja yang disimpan. Selain itu, jika solusi yang dicari berada pada level yang dalam dan paling kiri, maka DFS akan menemukannya secara cepat (Cormen dkk, 2009).

 

Berikut ini Algoritma Depth First Search (DFS) untuk Pencarian Rute Angkutan Umum Kota Makassar:

Melalui aplikasi ini pengguna dapat melakukan pencarian rute yang terdekat dari posisinya sekarang dengan memanfaatkan fasilitas dari GPS (global positioning system) dan juga formula yang mampu menghitung jarak antara titik koordinat pengguna dan titik koordinat rute angkutan umum. Arsitektur aplikasi yang dibangun adalah aplikasi pencarian rute angkutan umum, dimana pengguna mobile harus terkoneksi melalui jaringan internet untuk dapat mengetahui titik awal atau posisi dari si pengguna aplikasi. Kemudian menentukan alamat tujuan, dimana alamat tujuan tersebut telah dihubungkan kebeberapa titik koordinat yang sebelumnya telah diinputkan ke database server. Maka kesimpulannya, kini masyarakat pengguna angkutan umum di Kota Makassar dapat dengan mudah mengetahui informasi kode angkutan umum melalui smartphone dan mendapatkan solusi rute-rute angkutan umum yang terdekat dengan menggunakan algoritma DFS.

 

Sumber:

Rismayani, R., & Ardimansyah, A. (2015). Aplikasi Berbasis Mobile untuk Pencarian Rute Angkutan Umum Kota Makassar Menggunakan Algoritma Depth First Search. Jurnal Pekommas, Vol. 18 No. 3, 171 - 180.

rmdwirizki. (2014). Penelusuran Pohon Biner Algoritma DFS(Stack) dan Algoritma BFS(Queue) dalam Bahasa C. Dipetik Oktober 8, 2020, dari https://saungkode.wordpress.com/2014/04/16/penelusuran-pohon-biner-berdasarkan-kedalaman-dengan-algoritma-dfs-stack-dan-secara-melebar-level-order-dengan-algoritma-bfs-queue-dan-implementasinya-dalam-bahasa-c/