Cara Melakukkan Pencarian dengan Algoritma Breadth-First Search (BFS)

Konnichiwa sobat Otatechnime~

Post kali ini mimin akan menerangkan kepada kalian bagaimana cara melakukkan teknik pencarian dengan salah satu metode pencarian menggunakan algoritma BFS (Breadth-First Searching). Teknik ini merupakan teknik yang cukup banyak digunakan dalam melakukkan pencarian data. Sesuai namanya, teknik pencarian BFS menggunakan cara mencari secara melebar pada suatu hierarki data/tree.

Baca Juga : Pencarian DFS

Agar kalian lebih mudah untuk memahami cara mencarinya, mimin sediain langkah pencarian beserta gambar cara melakukkan teknik pencarian BFS berikut:

Langkah pencaraian dengan teknik BFS
1. Ketika melakukkan pencarian, sudah pasti kita memiliki data yang akan kita cari bukan? Maka itu untuk pemulaan kita butuhkan suatu hierarki data atau kumpulan dari data yang akan kita cari. Dipaparkan dalam bentuk graphic Tree sebagai berikut.

2. Pada gambar, kita memiliki sejumlah data dimana A sebagai root atau folder utama. Pada data A memiliki anak yaitu data B,C, dan D. Begitu pula data tersebut memiliki anak dan begitu seterusnya hingga data mencapai data M.
3. Pada contoh kali ini, kita akan mencari data yang dihendaki dengan menggunakan teknik BFS. Pencarian dilakukkan mulai dari root hingga ke childrennya atau ke anak-anakannya. Sebagai contoh,

Kita akan mencari data L

Pencarian dilakukkan mulai dari root yaitu dari A.

4. Nah, setelah kita tau data apa yang kita kehendaki untuk ditemukan, maka proses pencarian pun dimulai. Pertama, komputer akan memulai dari A sebagai starting point.

5. Setelah itu, kita cari mulai dari child dari root, untuk contoh kali ini yaitu B,C, dan D. Biasanya komputer akan melakukkan pencarian secara Random untuk memilih mana data yang akan dilalui terlebih dahulu, tapi untuk contoh kali ini kita tentukan data akan dicari mulai dari yang paling kiri yaitu data B. Lalu kita temukan bahwa B memiiliki child point lagi yaitu E dan F. Sampai sini, kita tentukan B menjadi salah satu kandidat pencarian.

6. Lalu kita pindah ke point berikutnya yaitu point C. Pada point C juga memiliki child point yaitu G dan H. C menjadi kandidat point. Lalu ke point selanjutnya yaitu point D.

7. Pada point D kita punya child I dan J. D menjadi kandidat point.

Perlu diingat, Pencarian BFS menggunakan metode queue FIFO (First In First Out), sehingga point-point seperti B,C, dan D antri untuk dicek apakah data tersebut adalah data yang dicari. 

8. Setelah child point dari A sudah terdeteksi semua, maka dilanjutkan mencari mulai dari point awal antara B,C dan D. Karena tadi kita mulai mencari dari B, maka kita lanjutkan pencarian menuju child dari B sesuai metode queue FIFO.

9. B memiliki child E dan F. Dimulai dari E. Lalu dicek apakah sudah sama dengan data yang kita cari? Jika belum maka pindah ke F. Jika masih tidak sama, maka pindah ke parent sebelumnya yaitu C.

10. Pada C memiliki child G dan H, lalu mulai dari G, apakah sudah sama? Jika belum kita pindah ke H. Apakah sudah sama? Jika belum, kita pindah lagi ke parent sebelumnya yaitu D.

11. Pada D, memiliki child I dan J, lalu mulai dari I. Apakah sudah sama? Karena masih belum sama, kita pindah ke J. Apakah sudah sama? Jika belum maka kita pindah ke parent E. Pada parent E karena bukan data yang dicari, maka lanjut ke childnya yaitu K.

12. K bukanlah data yang dicari makan ke parent selanjutnya yaitu F. Karena F tidak memiliki child lagi maka pindah ke G.

13. Pada G memiliki child L. Ketika kita sampai titik ini, ternyata L adalah data yang sama dengan yang kita cari. Dengan begitu pencarian pun dipastikan berhenti karena data L sudah berhasil ditemukan.

Jadi kurang lebihnya, begitu penjelasan bagaimana cara melakukkan pencarian dengan metode BFS.
Sekian penjelasan dari mimin semoga kalian mengerti dan dapat menerapkannya.

Sayonara~

Baca Juga : Pencarian DFS

Share this

Unknown