Kompleksitas Waktu dan Ruang

Kompleksitas Waktu:

• O(V + E)
  • Setiap vertex dimasukkan ke antrean dan dikeluarkan dari antrean satu kali, dan setiap edge diperiksa beberapa kali dengan jumlah yang konstan.

Kompleksitas Ruang:

• O(V + E)
  • Daftar ketetanggaan menyimpan setiap edge, dan antrean serta array visited menampung hingga V vertex.

Ringkasan:

• BFS menjelajahi graf secara berlapis menggunakan antrean, dengan mengunjungi vertex yang lebih dekat sebelum vertex yang lebih jauh.
• Urutan berlapis ini menjadikannya algoritma pilihan untuk mencari jalur terpendek pada graf tanpa bobot.