חיפוש לרוחב - חלק ראשון
בדפים הבאים נעסוק באלגוריתם
חיפוש לרוחב, באנגלית הוא נקרא Breadth-First-Search (או
בקצרה - BFS).
זהו אחד האלגוריתמים הפשוטים
ביותר לסריקת גרף ומשמש כ"אב-טיפוס" עבור אלגוריתמי
גרפים רבים, כדוגמת האלגוריתם של דייקסטרה
למציאת מסלולים קצרים ביותר ממקור יחיד ואלגוריתם פרים
למציאת עץ פורש מינימלי.
בהינתן גרף וקודקוד מסוים,
המשמש כמקור, חיפוש לרוחב בוחן בשיטתיות את קשתות הגרף,
כדי לגלות את כל הקודקודים הנגישים מקודקוד המקור.
בנוסף, מחשב האלגוריתם את המרחק (מספר הקשתות המינימלי)
מקודקוד המקור אל כל שאר הקודקודים בגרף. קודקו אשר לא נגיש
מקודקוד המקור הוא בעל מרחק אינסופי מקודקוד המקור.
האלגוריתם נקרא חיפוש לרוחב
מפני שהוא מגלה כל פעם את כל הקודקודים הנמצאים באותו מרחק
מקודקוד המקור, תחילה את הקודקודים הנמצאים מרחק של קשת
אחת מהמקור, לאחר מכן את הקודקודים המרוחקים שתי קשתות מן
המקור וכן הלאה.
האלגוריתם פועל הן על גרפים
מכוונים והן על גרפים לא מכוונים.
כדי לעקוב אחרי התקדמות האלגוריתם,
נצבע את הקודקודים בצבעים. תחילה כל הקודקודים יצבעו בלבן
(צבע המסמן שקודקוד עוד לא התגלה),
קודקודים אשר מתגלים לראשונה נצבעים באפור (הצבע מסמן שהקודקוד
התגלה, אך הטיפול בו עוד לא הסתיים).
לבסוף נשתמש בצבע השחור כדי לצבוע את הקודקודים שהטיפול
בהם הסתיים.
למעשה, הקודקודים הצבועים באפור משמשים כגבול בין הקודקודים
השחורים (שהטיפול בהם הסתיים) לקודקודים שעוד לא התגלו.
