Apa itu Algoritma Depth First Search? Pengertian dan Cara Kerjanya

Metode pencarian (searching) terbagi menjadi dua jenis yaitu pencarian buta (blind search) dan heuristic search. Salah satu contoh algoritma yang termasuk dalam pencarian buta adalah Depth First Search.

Depth first search adalah salah satu algoritma pencarian graf yang banyak digunakan dan sangat populer. Depth first Search atau Depth first traversal adalah algoritma rekursif yang dipakai untuk mencari semua simpul dari suatu graf atau tree. Traversal berarti mengunjungi semua node dari sebuah graf.

Daftar Isi

Pengertian Depth First Search

Depth First Search (biasa disebut DFS) pertama kali dipelajari pada abad ke-19 oleh matematikawan Prancis Charles Pierre Trémaux sebagai strategi untuk memecahkan labirin.

Depth First Search merupakan salah satu algoritma yang paling umum digunakan untuk melintasi atau melakukan pencarian pada struktur data graph atau tree dengan menggunakan teknik backtracking.

DFS juga dikenal sebagai Depth First Traversal jika kita menggunakannya dalam struktur data tree. Tree sendiri didefinisikan sebagai graph terhubung yang tidak mengandung sirkuit.

Algoritma Depth First Search (DFS) adalah suatu metode pencarian pada sebuah tree/pohon dengan menelusuri satu cabang sebuah tree sampai menemukan solusi. 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.

Cara Kerja Algoritma Depth First Search

Untuk memahami algoritma ini, bayangkan sebuah labirin.

Apa yang kita lakukan ketika harus memecahkan labirin? Kita akan mengambil rute, terus berjalan sampai kita menemukan jalan buntu. Setelah mencapai jalan buntu, kita mengambil jalan mundur sampai melihat jalan yang belum kita coba sebelumnya. Ambil rute baru itu. Begitu seterusnya terus sampai kita menemukan jalan buntu. Ambil jalan mundur lagi. Hingga kita bisa mendapatkan solusi atau jalan keluar.

Cara kerja algoritma depth first search hampir sama. Algoritma ini melakukan penelusuran simpul dengan pendekatan mendalam.

Algoritma DFS memiliki prioritas untuk mengunjungi simpul sampai level terdalam terlebih dahulu. Kemudian jika ditemukan jalan buntu (tidak ada lagi simpul yang bertetangga), algoritma akan memeriksa simpul sebelumnya yang sudah dikunjungi dan masih bertetangga dengan simpul lain yang belum dikunjungi dan menelusuri simpul tersebut.

Dengan kata lain, simpul cabang atau anak yang terlebih dahulu dikunjungi.

Gambar berikut adalah ilustrasi DFS

Pseucode

Di bawah ini adalah contoh pseudocode yang mengimplementasikan DFS baik secara rekursif maupun non-rekursif.

Algoritma ini umumnya berbasis LIFO (Last In First Out) berupa tumpukan (stack) untuk melacak node atau simpul yang dikunjungi. Node terakhir yang terlihat adalah yang berikutnya untuk dikunjungi dan sisanya disimpan untuk dikunjungi nanti.

Pseucode DFS recursive

procedure DFS(G,v):

   label v as discovered

   for all edges from v to w in G.adjacentEdges(v) do

      if vertex w is not labeled as discovered then

      recursively call DFS(G,w)

Pseucode DFS non-recursive:

procedure DFS-iterative(G,v):

      let S be a stack

      S.push(v)

      while S is not empty

            v ← S.pop() 

            if v is not labeled as discovered:

                label v as discovered

                for all edges from v to w in G.adjacentEdges(v) do

                    S.push(w)

Kelebihan Algoritma Depth First Search

Depth First Search memiliki kelebihan di antaranya adalah

Dapat menemukan solusi tanpa memeriksa banyak ruang pencarian sama sekali. Ini sangat penting jika ada banyak solusi yang dapat diterima. Depth First Search dapat berhenti ketika salah satunya ditemukan.
Depth First Search jauh lebih efisien untuk ruang pencarian dengan banyak cabang karena tidak perlu mengeksekusi semua simpul pada suatu level tertentu pada daftar open.
Depth First Search memerlukan memori yang relatif kecil karena node pada lintasan yang aktif saja yang disimpan.

Kelemahan Algoritma Depth First Search

Adapun kelemahan algoritma DFS, adalah:

Memungkinkan tidak ditemukannya tujuan yang diharapkan dan hanya akan mendapatkan satu solusi pada setiap pencarian.
Terdapat peluang tidak menemukan solusi optimal
Kemungkinan terjebak pada jalur pencarian yang tidak berguna.

Trivusi