DFS atau Depth-First Search merupakan metode penelusuran
struktur graf/pohon secara mendalam. Pada setiap iterasi , algoritma berlanjut
untuk titik yang belum dikunjungi, yang berdekatan dengan titik dimana
algoritma sedang berlangsung. Proses ini berlangsung hingga mencapai jalan
buntu/pencarian sudah tidak bisa kemana-mana lagi, kondisi ini terjadi ketika
titik yang tidak memiliki titik berdekatan yang belum dikunjungi telah ditemui.
Kita dapat menggunakan stack untuk melacark operasi depth-first
search, dengan mem-push simpul pada stack
ketika simpul dikunjungi untuk pertama kalinya. Lalu kita mem-pop simpul
tersebut jika pada simpul tersebut sudah tidak bisa kemana-mana lagi/buntu.
Selain itu juga kita dapat membuat depth-first
search forest, simpul awal graf traversal berfungsi sebagai akar dari pohon
pertama dalam hutan.
Berikut merupakan proses penelusuran dfs dengan menggunakan stack
a. Pertama kita tandai
semua simpul dengan 0, artinya simpul tersebut belum dikunjungi.
b. Masukkan simpul a ke
dalam stack, dari simpul a (anggap a adalah parent) kita berlanjut ke simpul
anak dari a yaitu c dan masukkan c ke dalam stack, dari simpul c kita lanjut ke
simpul d dan simpul d dimasukkan ke dalam stack.
c. Simpul d sudah
tidak memiliki anak lagi, dan d berada dikondisi jalan buntu. Sehingga pada
stack yang pertama kita keluarkan yaitu d. Dari d akan kembali ke c dan
disimpul c kita mengecek apakah ada anak dari c? Ternyata ada, yaitu simpul f.
Simpul f dimasukan ke dalam stack, dari simpul f kita melakukan penelusuran
kembali, kita melihat bahwa ada anak dari simpul f yaitu b. Simpul b kita
masukan ke dalam stack, dari simpul b penelusuran masih berlanjut karena masih
ada simpul yang belum dikunjungi, yaitu simpul e. Simpul e kita masukan ke dalam
stack, setelah itu c sudah tidak memiliki anak lagi dan berada dalam kondisi
jalan buntu, sehingga di stack ini kita mem-pop e, setelah itu pop b, pop f,
pop c, dan terakhir pop a.
d. Pada graf
selanjutnya kita lakukan hal seperti tadi yaitu kita tandai semua simpul dengan
0 yang berarti belum pernah dikunjungi.
e. Kita mulai dari
simpul g sebagai parent. Simpul g kita masukan ke dalam stack, selanjutnya
lakukan penelusuran dari simpul g ke simpul anaknya yaitu h, h kita masukan ke
dalam stack, dari h kia lakukan penulusuran kembali sehingga kita push i ke
dalam stack, dan yang terakhir push j ke dalam stack.
f. Karena pada simpul
j sudah jalan buntu maka kita pop j, pop i, pop , dan terakhir pop g.
Jika dalam stack
sudah kosong maka pencarian telah selesai dan hasil ditemukan.
Berikut merupakan
hasil dari DFS tadi:
A-C-D-F-B-E-G-H-I-J.
Dalam DFS ini terdapat dua kali pengurutan yang ditandai dengan angka
seperti gambar diatas. Angka yang berhimpitan dengan simpul itu merupakan
urutan saat simpul itu dimasukkan (push). Dan angka yang berada disebelah kanan
nya merupakan urutan pengeluaran (pop) simpul pada stack tadi.
Referensi: Buku Introduction to The Design and Analysis of Algorithms
Referensi: Buku Introduction to The Design and Analysis of Algorithms
