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

אלגוריתם חיפוש לרוחב (אנגלית: Breadth-first search, ראשי תיבות: BFS) הוא אלגוריתם המשמש למעבר על צומתי גרף, למשל לצורך חיפוש צומת המקיים תכונה מסוימת. הגרף יכול להיות מכוון או לא מכוון. צומת כלשהו בגרף נקבע להיות הצומת ההתחלתי ${\displaystyle V_{0}}$, והאלגוריתם עובר על כל הצמתים במרחק צלע אחת מ-${\displaystyle V_{0}}$, ואז על כל הצמתים במרחק 2 צלעות מ-${\displaystyle V_{0}}$ וכן הלאה. צורת חיפוש זו היא חיפוש לרוחב הגרף, בניגוד לחיפוש לעומק הגרף.

סדר סריקת הקודקודים בחיפוש לרוחב

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

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

סיבוכיות הזמן והמקום של האלגוריתם בגרף קשיר^[1] היא ${\displaystyle O(|V|+|E|)}$, כאשר ${\displaystyle V}$ מייצג את קבוצת הצמתים בגרף ו-${\displaystyle E}$ מייצג את קבוצת הקשתות בגרף.

תיאור אינטואיטיבי

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

תיאור פורמלי

הקוד להלן מתאר אלגוריתם חיפוש לרוחב המתחיל בצומת start ומחפש צומת goal,

קטע הקוד הבא הוא פסאודו קוד.

   function breadthFirstSearch (Start, Goal)
   { 
       enqueue(Queue,Start)
       setVisited(start)
       while notEmpty(Queue)
       {
           Node := dequeue(Queue)
           if Node = Goal
           {
               return Node
           }
           for each Child in Expand(Node)
           {
               if notVisited(Child)
               {              
                   setVisited(Child)
                   enqueue(Queue, Child)
               }
           }
       }
   }

ראו גם

• אלגוריתם חיפוש לעומק
• אלגוריתם חיפוש A*

קישורים חיצוניים

מדיה וקבצים בנושא אלגוריתם חיפוש לרוחב בוויקישיתוף

הערות שוליים

1. ובגרף מכוון, אם הוא קשיר היטב