Time and Space Complexity

تعقيد الوقت:

• O(V + E)
  • يتم إدراج كل رأس في الطابور وإخراجه منه مرة واحدة، ويتم فحص كل حافة عدداً ثابتاً من المرات.

تعقيد المساحة:

• O(V + E)
  • تخزن قائمة الجوار كل حافة، ويحتوي الطابور ومصفوفة العناصر التي تمت زيارتها على ما يصل إلى V من الرؤوس.

ملخص:

• يستكشف BFS في طبقات باستخدام طابور، حيث يزور الرؤوس الأقرب قبل الأبعد.
• هذا الترتيب الطبقي يجعله الخوارزمية المفضلة لأقصر المسارات في الرسوم البيانية غير الموزونة.