BFS dan DFS

Saat kita dalam perjalanan, rute yang efektif merupakan hal yang paling dicari oleh kita. Selain masalah jarak, rute yang bebas kemacetan juga menjadi hal yang jadi prioritas bagi masyarakat kita. Tapi di blog ini kita tidak akan mengukur seberapa efisien rute tersebut, atau berapakah kuantitas kendaraan yang melewati rute tersebut. Tapi kali ini saya akan membahas contoh pencarian rute melalui proses BFS dan DFS. Apakah itu?

BFS dan DFS merupakan suatu metode atau cara untuk menemukan solusi. Biasanya solusi dijabarkan dengan menggunakan rumus 'pohon' yang memiliki akar-akar yang panjang. Misalnya kita ingin mencari rute perjalanan dari Arad ke Bucharest, jika melalui peta yang terlihat seperti ini

Pada BFS (Breadth First Search), pencarian solusi dimana semua node pada level n akan ditelusuri terlebih dahulu. Contoh BFS

Sedangkan pada DFS (Depth First Search), pencarian solusi dengan menulusuri terlebih dahulu sampai akar-akarny. Jika tidak ketemu, pencarian akan pindah ke node yang lain di level yang sama. Contoh pencarian melalui DFS

Dibandingkan dengan BFS, keuntungan dari DFS yaitu, proses pencarian solusi membutuhkan sedikit memori dibandingkan dengan pencarian BFS karena pada pencarian DFS tidak perlu untuk menyimpan semua node pada setiap level. Untuk mengetahui lebih lanjut apa itu BFS dan DFS bisa di cek disini.