Metode DFS (Depth First Search)

PENGERTIAN DEPTH FIRST SEARCH

DFS (Depth-First-Search) adalah salah satu algoritma penelusuran struktur graf / pohon berdasarkan kedalaman. Simpul ditelusuri dari root kemudian ke salah satu simpul anaknya ( misalnya prioritas penelusuran berdasarkan anak pertama [simpul sebelah kiri] ), maka penelusuran dilakukan terus melalui simpul anak pertama dari simpul anak pertama level sebelumnya hingga mencapai level terdalam.

Setelah sampai di level terdalam, penelusuran akan kembali ke 1 level sebelumnya untuk menelusuri simpul anak kedua pada pohon biner [simpul sebelah kanan] lalu kembali ke langkah sebelumnya dengan menelusuri simpul anak pertama lagi sampai level terdalam dan seterusnya.

Contoh pohon biner Depth First Search :

 Maka, urutan penelusurannya adalah : A – B – D – H – E – I – C – F – G – J – K – L

Dalam implementasinya DFS dapat diselesaikan dengan cara rekursif atau dengan bantuan struktur data stack. Kita akan membahas dengan cara yang menggunakan stack. Stack yang digunakan adalah stack yang isi elemennya adalah simpul pohon / tree. Bagaimana cara kerjanya ? Berikut ini adalah urutan algoritmanya :

-  Masukkan simpul root ke dalam tumpukan dengan push.
- Ambil dan simpan isi elemen (berupa simpul pohon) dari tumpukan teratas.
- Hapus isi stack teratas dengan prosedur pop.
- Periksa apakah simpul pohon yang disimpan tadi memiliki anak simpul.
- Jika ya, push semua anak simpul yang dibangkitkan ke dalam stack.
- Jika tumpukan kosong berhenti, tapi jika tidak kembali ke langkah dua.

Jadi, untuk gambar pohon biner di atas urutan langkah dan kondisi stack-nya setiap iterasi adalah :

Contoh diatas menggunakan prioritas untuk memasukkan anak simpul dari sebelah kanan terlebih dahulu ke dalam stack. Sehingga, pada iterasi 2 elemen A dihapus lalu memasukkan anak simpulnya yaitu C dulu, baru B ke dalam stack. Selain itu bisa dilihat stack teratas (yang diwarna biru) pada tiap iterasi memiliki urutan A – B – D – H – E – I – C – F – G – J – K – L. Oiya, pada iterasi ke 13 itu kondisi stack sudah kosong karena ketika simpul J dibangkitkan tidak ada anak simpul yang dimasukkan ke stack.

Sumber : https://onbuble.wordpress.com/2011/05/26/6/