סיבוכיות זמן ומקום

סיבוכיות זמן:

• O(V + E)
  • כל קודקוד נכנס לתור ויוצא ממנו פעם אחת, וכל קשת נבדקת מספר קבוע של פעמים.

סיבוכיות מקום:

• O(V + E)
  • רשימת השכנויות מאחסנת כל קשת, והתור ומערך הקודקודים שבוקרו מכילים עד V קודקודים.

סיכום:

• BFS סורק בשכבות באמצעות תור, ומבקר בקודקודים הקרובים יותר לפני הרחוקים יותר.
• הסדר השכבתי הזה הופך אותו לאלגוריתם המועדף למציאת מסלולים קצרים ביותר בגרפים לא משוקללים.