מבוא

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

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

כמו בשאר חלקי הסדרה, הגרף נתון באמצעות n (מספר הקודקודים, 0 עד n - 1) ו-edges, מערך שטוח של זוגות לא מכוונים [u0, v0, u1, v1, ...].

בואו נתחיל!