Breadth-First & Depth-First Search

Dulu saat masih kuliah, ada beberapa mata kuliah yang mengajarkan algoritma searching seperti Kecerdasan Buatan, Algoritma & Struktur Data, juga Desain & Analisa Algoritma. Ketiganya juga membahas dua buah algoritma searching yaitu Breadth-First Search dan Depth-First Search.

Saat hari ini saya membuka-buka kembali buku-buku kuliah, saya kembali teringat kedua algoritma tersebut (walaupun dulunya juga tidak begitu perduli ada algoritma ini itu). Benar juga, selama ini jika dihadapkan dengan masalah-masalah yang berhubungan dengan searching tree saya tidak pernah menerapkan algoritma-algoritma yang dulu saya pelajari saat kuliah. Kebanyakan adalah menggunakan ide dan pemikiran yang muncul saat menghadapi persoalan-persoalan tersebut.

Setelah membaca beberapa halaman buku kuliah yang iseng-iseng saya buka tersebut (baca-baca lagi karena dulu amat sangat jarang membuat catatan hehehe...), terlintas kembali bagaimana logika algoritma tersebut. Untuk menyederhanakannya sebaiknya kita gunakan contoh tree berikut

Misalkan kita ingin mencari apakah ada path dari A menuju G. Node - node mana saja yang akan kita lewati? Kita akan menggunakan sebuah list yang berisi node-node yang dilewati oleh algoritma searching tersebut.

Pada saat awal, list akan berisi node awal yaitu A, {A}. Selanjutnya dari node A akan menuju node B dan C, jangan lupa menghapus node A dari list karena telah digantikan oleh node B dan C, {B, C}. Selanjutnya adalah menghapus B dari list dan menggantinya dengan node D dan E, {C, D, E}. Ingat bahwa breadth-first memperlakukan node yang memiliki depth terendah lebih dulu sehingga D dan E diletakkan setelah C karena D dan E memiliki depth 3 sedangkan C memiliki depth 2 (sama dengan B). Selanjutnya kita menghapus C dan menggantinya dengan F dan G sehingga list akan berisi {D, E, F, G}. Akhirnya node G ditemukan juga dan membuat searching berakhir dengan sukses.

Bagaimana jika menggunakan depth-first search? Pertama kali list berisi node A, {A}. Kemudian A dihapus dari list dan diganti dengan B dan C, {B, C}. Selanjutnya B diganti dengan D dan E dengan meletakkan keduanya di depan (kebalikan breadth-first), {D, E, C}. Karena D dan E berupa leaf maka keduanya bisa dhapus dari list sehingga tersisa C, {C}. Kemudian node C diganti dengan F dan G, {F, G}. Node G ditemukan dan proses searching berakhir dengan sukses.

Jika digambarkan, maka urut-urutan node mana yang diproses terlebih dahulu pada breadth-first search akan terlihat seperti berikut

Sedangkan jika menggunakan depth-first search akan terlihat urut-urutan node yang diproses seperti berikut