ANALISA ALGORITMA DEPTH-FIRST SEARCH

ANALISA ALGORITMA DEPTH-FIRST SEARCH

UNTUK PENCARIAN RUTE TERPENDEK

Lindung Budiyantoro

Jurusan Teknik Informatika, Fakultas Teknik, Universitas Trunojoyo

Jl. Raya Telang PO. BOX 2 Kamal, Bangkalan

ABSTRAK

Pencarian rute terpendek merupakan suatu permasalahan yang sering kita jumpai dalam dunia nyata. Masalah ini tidak hanya menyangkut tentang mendapatkan jarak terdekat untuk mencapai tujuan, tetapi juga berhubungan dengan efektivitas dan efisiensi waktu dan biaya yang akan dikeluarkan. Algoritma Depth-First Search merupakan suatu langkah-langkah pencarian mendalam yaitu dengan cara mengunjungi atau melewati anak suatu simpul sebelum mengunjungi simpul tetangganya. Dalam pencarian jarak terpendek akan  dihasilkan suatu jalur yang akan dilewti untuk mencapai suatu tujuan atau menemukan jalur menuju sasaran.

Kata Kunci: rute terpendek, Depth-First Search

1          PENDAHULUAN

---

Permasalahan dalam pencarian rute terpendek adalah mencari jarak terdekat untuk mencapai suatu tujuan. Akan tetapi, hal ini bisa dikembangkan untuk mencari biaya minimum dan waktu tempuh tersingkat. Intinya adalah untuk mendapatkan penyelesaian yang efektif dari suatu persolan yang dihadapi.

Algoritma Depth-First Search merupakan salah satu algoritma yang sering digunakan untuk melakukan pencarian rute terpendek. Algoritma ini akan mencari atau mengunjungi anak dari suatu simpul sebelum simpul tetangganya.

2          DEPTH-FIRST SEARCH

---

2.1    Pengertian Depth-First Search

Depth-first search (DFS) melakukan pencarian secara preorder. Mengunjungi anak suatu simpul sebelum simpul tetangganya.

Berikut gambar yang mengiilustrasikan urutan simpul yang dikunjungi pada algoritma DFS:

Gambar Ilustrasi urutan kunjungan simpul pada algoritma DFS

Dari gambar, dapat dilihat bahwa dengan algoritma DFS, setiap anak simpul pertama yang bertetangga dengan simpul akar dikunjungi sampai tingkat terdalamnya lebih dahulu, lalu seluruh simpul pada subpohon tersebut, sebelum simpul lain yang juga bertetangga dengan simpul akar.

2.2    Algoritma DFS

Berikut ini adalah algoritma Depth-First Search :

procedure DFS(input v:integer)

Mengunjungi seluruh simpul graf dengan algoritma pencarian DFS

Masukan: v adalah simpul awal kunjungan

Keluaran: semua simpulyang dikunjungi ditulis ke layar

Deklarasi

   w : integer

Algoritma:

   write(v)

   dikunjungi[v]¬true

   for tiap simpul w yang bertetangga dengan simpul v do

      if not dikunjungi[w] then

          DFS(w)

      endif

   endfor

3          SKENARIO UJI COBA

---

Pencarian rute terpendek dilakukan dengan cara membuat simpul-simpul yang menjadi titik awal, titik-titik yang akan dilalui dan juga titik akhir sebagai akhir dari tujuan atau sebagai simpul yang dicari.

Dalam algoritma DFS, simpul yang telah dikunjungi disimpan dalam suatu tumpukan (stack). Antrian ini digunakan untuk mengacu simpul-simpul yang akan dikunjungi sesuai urutan tumpukan (masuk terakhir, keluar pertama) dan mempermudah proses runut-balik jika simpul sudah tidak mempunyai anak (simpul pada kedalaman maksimal).

Untuk memperjelas cara kerja algoritma DFS beserta tumpukan yang digunakannya, berikut langkah-langkah algoritma DFS:

1. Masukkan simpul ujung (akar) ke dalam tumpukan

2. Ambil simpul dari tumpukan teratas, lalu cek apakah simpul merupakan solusi

3. Jika simpul merupakan solusi, pencarian selesai dan hasil dikembalikan.

4. Jika simpul bukan solusi, masukkan seluruh simpul yang bertetangga dengan simpul tersebut (simpul anak) ke dalam tumpukan

5. Jika tumpukan kosong dan setiap simpul sudah dicek, pencarian selesai dan mengembalikan hasil solusi tidak ditemukan

6. Ulangi pencarian dari langkah kedua

4          HASIL UJI COBA

---

4.1    Keuntungan Dari Algoritma Depth-First Search

• Membutuhkan memori yang relative kecil, karena hanya node-node pada lintasan yang aktif saja.
• Secara kebetulan, metode depth-first search akan menemukan solusi tanpa harus menguji lebih banyak lagi dalam ruang keadaan.

4.2    Kelemahan Dari Algoritma Depth-First Search

• Memungkinkan tidak ditemukannya tujuan yang diharapkan.
• Hanya akan menemukan satu solusi pada setiap pencarian.

5           KESIMPULAN

---

Algoritma Depth-First Search bisa digunakan untuk melakukan pencarian rute terpendek. Dengan memperhatikan keuntungan dan kelemahan dari algoritma tersebut, bisa diambil kesimpulan bahwa algoritma ini bisa membantu pencarian rute terpendek, sehingga bisa mendapatkan penyelesaian yang efektif.

Algoritma Depth-First Search akan berhenti melakukan pencarian jika sudah ditemukan tujuan akhir.

6           DAFTAR PUSTAKA

---

[1]     Adi, G.N., Syauqi, A.L., dan Ahsanaa, Y., “Analisis Algoritma Pencarian Rute Terpendek Dengan Algoritma Dijkstra dan Bellman-Ford”.

[2]     Kustanto, Cynthia., Mutia, Ratna., dan Viqarunnisa, Pocut., “Penerapan Algoritma Breadth-first Search dan Depth-first Search Pada FTP Search Engine for ITB Network”.

[3]     Madanella, E.D.M., “Analisis Penggunaan Algoritma Pencarian Melebar (BFS) dan Algoritma Pencarian Mendalam (DFS) dalam Teori Graf”.

[4]     Munir, R., “Algoritma Traversal di dalam Graf”.

[5]     Syafidtri, N.A., “Robot Micronouse Dengan Menggunakan Algoritma Depth-First Search”.

[6]     Template makalah mengacu pada Jurnal Ilmiah Teknologi Informasi (JUTI) Fakultas Teknologi Infornasi - ITS Surabaya.