מוטיבציה

שיעור 2 מתוך 9 בקורס חיפוש לרוחב – אלגוריתמים על גרפים של Coddy.

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

מסלולים קצרים ביותר: בגרף לא משוקלל, BFS מוצא את המסלול בעל מספר הקשתות הקטן ביותר מנקודת ההתחלה לכל קודקוד אחר.
פשוט וליניארי: זמן הריצה הוא O(V + E) עם תור וסמן ביקור.
בכל מקום: המעברים הקצרים ביותר ברשתות, סולמות מילים, פתרון מבוכים וסריקת עצים לפי סדר רמות — כולם BFS.

כמו ב-DFS, אנחנו מכניסים לתור את השכנים של קודקוד בסדר עולה כדי שהתוצאות יהיו צפויות.

נסו בעצמכם

השיעור הזה לא כולל אתגר קוד.