אלגוריתם חיפוש לרוחב

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

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

תוצאת האלגוריתם היא עץ חיפוש לרוחב. העץ נותן מסלול מהשורש לכל צומת שמכיל הכי מעט קשתות שאפשר. בגרף ללא משקלים על הקשתות (כל קשת נחשבת לצעד אחד) זה גם המסלול הקצר ביותר.

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

האלגוריתם הבסיסי מתחיל בצומת Start ומחפש Goal:
1. enqueue(Queue, Start)
2. setVisited(Start)
3. while Queue לא ריק:
a. Node := dequeue(Queue)
b. אם Node = Goal, החזר את Node
c. עבור כל Child ב-Expand(Node):
אם Child לא נבדק: setVisited(Child); enqueue(Queue, Child)

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

מתחילים מנקודה אחת. קודם בודקים את כל הנקודות שמחוברות אליה ישירות. אחר כך בודקים את הנקודות שמחוברות למאלה.

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

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

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

1. enqueue(Start)
2. סמן Start כנבדק
3. while התור לא ריק:
- הוצא צומת מהתור
- אם זו המטרה, עצור
- אחרת הוסף את השכנים שלא נבדקו