Motivasi

BFS menggunakan queue (masuk pertama, keluar pertama) agar simpul diproses tepat sesuai urutan saat ditemukan, sehingga penelusuran berlangsung lapis demi lapis.

Mengapa belajar BFS?

• Jalur terpendek: pada graf tanpa bobot, BFS menemukan jalur dengan jumlah sisi paling sedikit dari titik awal ke setiap simpul lainnya.
• Sederhana dan linear: BFS berjalan dalam O(V + E) dengan queue dan penanda yang menunjukkan simpul telah dikunjungi.
• Digunakan di mana-mana: mencari lompatan terpendek dalam jaringan, permainan kata berjenjang, menyelesaikan labirin, dan penelusuran pohon berdasarkan urutan level semuanya menggunakan BFS.

Seperti DFS, kita memasukkan tetangga sebuah simpul ke queue dalam urutan menaik agar hasilnya dapat diprediksi.