Siprianus Blog: Depth First Search (DFS)

Searching adalah salah satu metode penyelesaian masalah dengan teknik pencarian solusi pada permasalahan tersebut.
Graph merupakan representasi dari himpunan Vertex dan Edge. Dalam kehidupan sehari-hari bisa di gambarkan oleh himpunan kota dan himpunan jalan yang saling berhubungan ataupun tidak. Untuk penelusuran vertex – vertex tersebut ada dua algoritma yang bisa digunakan, yakni :

Algoritma DFS (Depth First Search)

Algoritma DFS, yakni algoritma yang menelusuri vertex secara mendalam terlebih dahulu. Dengan kata lain algoritma ini menelusuri vertex sampai anak cabangnya, hingga tidak ditemukan anak cabang lain. Algoritma ini memiliki kelebihan, yakni cepat mencapai ruang kedalaman. Namun terdapat kekurangan, yakni menghabiskan waktu yang banyak jika suatu Graph memiliki lintasan yang panjang ( anak cabang banyak ). Algoritma DFS dalam penelusurannya menggunakan stack.

Untuk lebih memperjelas, bisa dilihat contoh di bawah ini :

Hasil Penelusuran dengan DFS :

A B E G F C H D

Penelusuran DFS pada Graph G1, penjelasannya adalah sebagai berikut :

Pertama Kali, penelusuran dimulai dengan vertex dengan abjad paling rendah (A), kemudian penelusuran dilanjutkan dengan mencari anak cabang (adjacent) terdekat dari A, dan lanjutkan penelusuran ke vertex dengan abjad yang lebih rendah, yakni B. Ketika berada di B, terdapat dua cabang, pilih vertex yang lebih rendah yakni E dan dilanjutkan ke vertex G. Sekarang penelusuran sudah berada di G, namun anak cabang dari G kembali lagi ke A yang sudah pernah di telusuri. Maka, penelusuran akan kembali ke anak cabang level sebelumnya untuk mencari anak cabang lain. Dalam konteks diatas, dari G akan kembali ke E, karena tidak ada lagi adjacent maka akan kembali ke B. Dari B akan di lanjutkan ke C lalu dilanjutkan ke H, kembali ke C dan kembali ke F lalu dilanjutkan ke D. Vertex D merupakan penelusuran terakhir dari Algoritma ini, karena semua vertex sudah dikunjungi.

Tampilan DFS setelah dikunjungi