Page 7 - Searching bismillah

ii. Breadth-First Search (BFS)
Strategi searching BFS merupakan suatu pencarian yang dilakukan

pada semua node pada setiap level secara berurutan dari kiri ke kanan.
Apabila pada satu level belum ditemukan solusi, maka pencarian

dilanjutkan pada level berikutnya, demikian seterusnya sampai
ditemukan solusi. Penggunaan strategi BFS dalam searching, dapat

diperoleh solusi yang ditemukan merupakan yang paling baik (optimal),
akan tetapi strategi pencarian BFS harus menyimpan semua node dalam

suatu antrian. Antrian tersebut digunakan untuk mengacu node
bertetangga yang akan dikunjungi kemudian sesuai urutan pengantrian.

Berikut Langkah-langkah cara kerja BFS:

1. Memasukkan node ujung ke dalam antrian
2. Mengambil node dari awal antrian, kemudian dicek apakah node
tersebut merupakan solusi

3. Apabila node tersebut merupakan solusi, pencarian dan hasil akan

dikembalikan
4. Apabila node bukan solusi, semua node yang bertetangga dengan

node tersebut dimasukkan dalam antrian
5. Apabila antrian kosong dan semua node sudah dicek, pencarian

telah selesai dan hasil solusi tidak ditemukan.
Gambar 2 mengilustrasikan pembangkitan pohon BFS .

Kelebihan BFS adalah :
• Tidak menemukan jalan buntu

• Apabila ada satu solusi, maka BFS akan menemukannya
• Apabila menemukan lebih dari satu solusi, maka solusi minimum

akan ditemukan
Kelemahan BFS adalah :

• Penggunaan memori yang cukup besar, karena menyimpan
semua node