Breadth First Search: Pengertian, Kelebihan dan Contoh

Apa itu Breadth First Search?

Breadth First Search (BFS) merupakan salah satu algoritma pencarian jalur melewati semua titik, yang dilakukan dengan mengunjungi node pada level n atau titik awal terlebih dahulu sebelum mengunjungi node-node pada level n+1 atau cabang titik secara terurut. 

Apabila titik tujuan belum ditemukan, maka perhitungan dapat diulang kembali pada masing-masing titik cabang dari setiap titik hingga sampai pada titik tujuan tersebut ditemukan. Singkatnya, algoritma BFS digunakan untuk melewati dan mencari semua node dengan struktur data tree maupun graph.

Algoritma BFS membutuhkan sebuah antrian q  yang digunakan untuk menyimpan node yang telah dikunjungi. Node-node tersebut diperlukan sebagai rujukan untuk mengunjungi node-node lain yang bersebelahan dengan node tersebut. 

Setiap node yang telah dikunjungi hanya masuk satu kali ke dalam antrian. Hal tersebut dikarenakan algoritma BFS memerlukan table Boolean agar dapat menyimpan node yang telah dikunjungi sehingga tidak ada node yang dikunjungi lebih dari satu kali.

Algoritma BFS berbeda dengan algoritma DFS. DFS merupakan kepanjangan dari Depth First Search, menjadi salah satu algoritma  yang dapat melewati struktur data tree maupun graph menggunakan teknik backtracking.

Adapun cara untuk mengimplementasikan algoritma BFS yakni hanya dengan pseudocode. Pseudocode merupakan salah satu cara penulisan program yang informal dan dapat dirancang dengan kaidah yang telah ditentukan sendiri sesuai urutan logika dan mudah dipahami.

Berdasarkan gambar di atas, berikut langkah-langkah yang dapat dijalankan.

1. (G, s) merupakan input, G merupakan grafik dan s merupakan simpul akar.
2. Antrian Q dirancang dan dan diasosiasikan dengan node sumber s.
3. Seluruh node anak dari s ditandai.
4. S diekstrak dari antrian dan kunjungi node anak atau cabang.
5. Semua simpul cabang diproses mulai dari v.
6. Node cabang w disimpan di Q untuk mengunjungi node turunannya lebih lanjut.
7. Melanjutkan hingga Q kosong.

Cara Kerja Breadth First Search

Node-node yang telah dikunjungi dapat tersimpan dalam suatu antrian algoritma BFS. Antrian tersebut dapat dimanfaatkan sebagai rujukan node yang bersebelahan dengannya yang akan dikunjungi selanjutnya sesuai dengan urutan pengantrian.

Sebelum melanjutkan pada pembahasan cara kerja, ada baiknya perlu mengetahui dan terbiasa pada struktur data utama yang berhubungan dengan algoritma breadth first search. Salah satu struktur data yang mengikuti prinsip breadth first search adalah Queue.

Queue merupakan struktur data yang terbuka di kedua ujung, yang mana satu ujung selalu digunakan untuk menginput data atau enqueue dan di ujung lainnya digunakan untuk menghapus data atau dequeue.

Adapun cara kerja algoritma BFS beserta antrian yang digunakan untuk memperjelas pemahaman, berikut langkah-langkah yang perlu diketahui.

• Pertama-tama, masukkan ujung atau akar ke dalam antrian.
• Kedua, ambil node dari antrian awal, kemudian periksa kembali apakah node tersebut merupakan solusi.
• Ketiga, apabila node tersebut merupakan solusi, maka pencarian dapat diselesaikan dan hasil dapat dikembalikan.
• Namun apabila node tersebut bukan merupakan solusi, maka dapat memasukkan semua node yang bersebelahan dengan node anak ke dalam antrian.
• Apabila antrian kosong dan setiap simpul telah diperiksa, maka pencarian dapat diselesaikan dan hasil dapat dikembalikan sebagai solusi tidak ditemukan.
• Langkah terakhir, ulangi kembali pencarian dari langkah kedua.

Kelebihan Breadth First Search

Adapun kelebihan yang dimiliki oleh breadth first search yang perlu diketahui, berikut di antaranya.

• Tidak akan menjumpai jalan buntu.
• Dapat dipastikan menemukan solusi yang dicari.
• Apabila terdapat satu solusi maka breadth first search dapat menemukannya.
• Dapat menjamin menemukan solusi apabila memang ada solusinya dan solusi yang telah ditemukan pasti dianggap paling baik.

Kekurangan Breadth First Search

Adapun kekurangan yang ada dalam breadth first search yang perlu dipahami, antara lain sebagai berikut.

• Memerlukan waktu yang cukup lama untuk memeriksa semua node yang ada.
• Apabila node jauh maka membutuhkan waktu yang cukup lama untuk memeriksa lintasan.
• Membutuhkan memori atau tempat penyimpanan yang cukup besar, hal tersebut disebabkan oleh metode ini dapat memeriksa secara menyeluruh node yang ada dalam satu pohon.

Contoh Breadth First Search

Dalam upaya memperjelas pemahaman berikut ini contoh grafik yang akan digunakan untuk melintasi algoritma breadth first search. 

Pada kasus ini, node a dapat dianggap sebagai simpul akar dan mulai melewati ke bawah dan mengikuti langkah-langkah yang telah disebutkan sebelumnya.

Gambar di atas menunjukkan bahwa proses end-to-end dari algoritma breadth first search. Selanjutnya berikut penjelasan dari gambar di atas.

1. Pada node a dapat dianggap sebagai noed akar dan masukkan ke dalam antrian.
2. Selanjutnya ekstrak node a dari antrian awal dan masukkan node anak cabang a, yaitu node b dan c.
3. Lalu cetak node a.
4. Setelah itu dapat dilihat antrian tidak kosong dan memiliki node b dan node c. Node b merupakan simpul pertama dalam antrian, oleh karena itu harus di ekstrak dan kemudian dimasukkan node anak dari b yaitu node d dan node e.
5. Terakhir, ulangi kembali langkah ini hingga antrian kosong. Adapun hal yang perlu diperhatikan adalah bahwa node yang sudah dikunjungi tidak dapat ditambah lagi ke dalam antrian. Hal tersebut dikarenakan node hanya dapat dilewati satu kali saja.