Halo sobat dira, kali ini kami akan menjelaskan apa itu BFS dan DFS. Seperti yang kita ketahui bahwa BFS dan DFS merupakan teknik pencarian yang bisa kita lakukan pada struktur data Graph.
Apa itu BFS?
BFS merupakan singkatan dari Breadth First Search yang merupakan teknik penelusuran data yang dimulai dari tetangga yang paling terdekat terlebih dahulu. Kelebihan dari teknik pencarian ini merupakan :
- Ketika menggunakan teknik ini , maka kita tidak akan menemukan jalan buntu
- Menjamin ditemukannya sebuah solusi jika solusi tersebut tersedia
Kekurangan dari teknik BFS merupakan :
- ketika melakukan proses penelusuran BFS akan memakan memori yang banyak
- Dalam melakukan proses penelusuran BFS selain memakan memori, BFS akan memakan waktu juga karena proses penelusuran yang begitu lama
Sedangkan DFS merupakan singkatan dari Depth First Search yang melakukan proses penelusuran data yang dimulai dari tetangga terjauh terlebih dahulu. Kelebihan dari DFS merupakan :
- Dalam melakukan proses penelusuran DFS memakan memori yang tidak begitu banyak
- Jika solusi yang dicari berada pada level yang dalam paling kiri, DFS akan cepat menemukannya.
Mari kita lihat dari studi kasus dari graph diatas, kita mulai dengan teknik pencarian BFS, Kita mulai dari node A , sekarang lihat tetangga dari node A, yaitu node B dan E lalu kita kunjungi node B dari node B kita kembali ke node A lalu kunjungi node E dari node E kita kembali ke node A lalu kita kunjungi lagi node B,dari node B , kita kunjungi tetangga dari node B , dari node B kita lilhat tetangganya yaitu node C kenapa node C ? karena node C merupakan tetangga terjauh dari node B sesuai dengan prinsip BFS yaitu, kita kunjungi tetangga terjauh terlebih dahulu lalu kita kunjungi tetangga terdekat. Mari kita lanjut, lalu karena node C tidak memiliki tetangga lagi, maka kita kembali ke node B , lalu dari node B kita kunjungi node D karena node D tidak memiliki tetangga maka proses pencarian sudah selesai dan hasil dari penelusurannya adalah : A,B,E,C,D.
Lalu kita coba dengan teknik DFS , seperti yang kita ketahui teknik DFS mengunjungi tetangga terdekatnya , maka kita mulai dari node A, setelah melihat tetangganya , kita kunjungi node B karena node B merupakan tetangga dari A , setelah itu, kita lihat tetangga dari B lalu kita hubungi node C karena node C merupakan tetanga dari node B lalu kita kembali lagi ke node B dan kita kunjungi tetangga lain selain node C yaitu node D lalu dari node B kita kembali lagi ke node A lalu mengunjungi tetangga nya selain node B yaitu node E, setelah itu karena tidak ada lagi tetangga maka proses penelusuran berakhir dan hasil dari penelusuran DFS yaitu : A,B,C,D,E
Maka dapat disimpulkan bahwa setiap teknik penelusuran terdapat kelebihan dan kekurangannya masing-masing dan hasil nya pun berbeda-beda berdasarkan dari studi kasus yang kita contohkan.
Sekian terimakasih, nantikan artikel-artikel kami berikutnya :)
