Depth-First Search dengan Stack

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