אלגוריתם חיפוש לרוחב – הבדלי גרסאות

מ
הגהה
אין תקציר עריכה
מ (הגהה)
 
[[קובץ:Breadth-first-tree.svg|250px|ממוזער|סדר סריקת הקודקודים בחיפוש לרוחב]]
'''אלגוריתם חיפוש לרוחב''' ([[אנגלית]]: '''Breadth-first search''', [[ראשי תיבות]]: '''BFS''') הוא [[אלגוריתם]] המשמש למעבר על צומתי [[גרף (תורת הגרפים)|גרף]], לרוב תוך [[אלגוריתם חיפוש|חיפוש]] צומת המקיים תכונה מסוימת. צומת כלשהו בגרף נקבע להיות הצומת ההתחלתי <math>V_0</math>, והאלגוריתם עובר על כל הצמתים במרחק צלע אחת מ-<math>V_0</math>, ואז על כל הצמתים במרחק 2 צלעות מ-<math>V_0</math> וכן הלאה . צורת חיפוש זו היא חיפוש לרוחב הגרף, בניגוד ל[[אלגוריתם חיפוש לעומק|חיפוש לעומק הגרף]].
 
חיפוש לרוחב סורק את הגרף בצורה שמבטיחה שכל צומת שנמצא באותו [[גרף קשיר#רכיבי קשירות|רכיב קשירות]] של הצומת ההתחלתי ייבדק, וסריקה זו נעשית בזמן אופטימלי, הליניארי למספר הקשתות והצמתים בגרף. בשל כך, חיפוש לרוחב מהווה בסיס לאלגוריתמים רבים שפועלים על גרפים, בהם [[אלגוריתם דייקסטרה]], [[האלגוריתם של פרים]] ו[[שיטת פורד-פלקרסון#%D7%90%D7%9C%D7%92%D7%95%D7%A8%D7%99%D7%AA%D7%9D %D7%90%D7%93%D7%9E%D7%95%D7%A0%D7%93%D7%A1-%D7%A7%D7%90%D7%A8%D7%A4|האלגוריתם של אדמונדס-קארפ]].
1,126

עריכות