Menguasai Algoritma Pencarian Depth First Search

Seperti kita ketahui bahwa metode pencarian breadth first search kurang efisien untuk pencarian, Oleh karena itu kehadiran metode depth first search untuk menjawabnya. Berbeda dengan breadth first search yang melakukan pencarian dari arah menyamping dan satu level node atau titik, depth first search memiliki pendekatan berbeda yaitu kedalaman. Pada algoritma ini melakukan penelurusan solusi melalui level terdalam untuk kemudian kembali menuju level berikutnya.

Seperti kita berjalan di pasar tradisional dengan keramaiannya mencari bahan masakan yang dibutuhkan. Jika kita memang belum pernah mengenal posisi dan penjual dipasar tersebut, maka kita akan menyusuri penjual lorong demi lorong. Jika belum ketemu maka berpindah lorong berikutnya, kita lakukan hingga benar-benar menemukan barang yang sesuai.

Prinsip pencarian buta menggunakan prinsip pencarian terdalam dulu memiliki kesamaan dengan pencarian di pasar tersebut. Sehingga proses akan menemukan solusi dengan pasti.

Namun, depth first search melakukan pencarian lebih baik daripada pencarian breadthfirst search. Walaupun sama-sama pasti menemukan solusi, pencarian terdalam tidak perlu mencari disetiap titik. Sehingga sistem dapat menghemat memori.

Pencarian terdalam dahulu seperti pada gambar diatas memiliki alur yang berbeda dengan breadth first search. Kita melihat alur pencarian dimulai dari S dan berakhir dengan tujuan yaitu titik G. Pencarian terdalam dimulai dari S kemudian diikuti titik atau level didalam sebelah kiri yaitu A kemudian sampai terdalam yaitu C. Kemudian dilanjutkan pada level titik yang sama jika belum menemukan solusi yaitu langkah D. Kemudian berpindah level yaitu titik B. Lakukan langkah tadi secara berulang sampai menemukan solusi.

Proses perulangan dilakukan sampai pada kondisi apa?. Tahap perulangan sampai solusi berada pada titik G. Dengan begitu solusi ditemukan, namun pada pemrograman dapat kita gunakan dengan ‘if-else’ atau ‘jika-maka’. Logikanya begini, jika solusi sama yang ditemukan sama dengan tujuan yaitu G, maka perulangan akan berhenti.