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

תוכן שנמחק תוכן שנוסף
אין תקציר עריכה
ביטול גרסה 15159829 של 84.109.15.3 (שיחה), שחזור
שורה 1:
[[תמונה:Breadth-first-tree.svg|200pxשמאל|ממוזער|סדר סריקת הקודקודים בחיפוש לרוחב]]
'''ליאלגוריתם וינרחיפוש פרחה.לרוחב''' ([[אנגלית]]: '''Breadth-first search''', [[ראשי תיבות]]: '''BFS''') הוא [[אלגוריתם]] המשמש למעבר על צמתי [[תורת הגרפים|גרף]], לרוב תוך [[אלגוריתם חיפוש|חיפוש]] צומת המקיים תכונה מסוימת. צומת כלשהו בגרף נקבע להיות הצומת ההתחלתי <math>V_0</math>, והאלגוריתם עובר על כל הצמתים במרחק צלע אחת מ<math>V_0</math>, ואז על כל הצמתים במרחק 2 צלעות מ<math>V_0</math> וכן הלאה . צורת חיפוש זו היא חיפוש לרוחב הגרף, בניגוד ל[[אלגוריתם חיפוש לעומק|חיפוש לעומק הגרף]].
 
חיפוש לרוחב סורק את הגרף בצורה שמבטיחה שכל צומת שנמצא באותו [[רכיב קשירות]] של הצומת ההתחלתי ייבדק, וסריקה זו נעשית בזמן אופטימלי, הלינארי למספר הקשתות והצמתים בגרף. בשל כך, חיפוש לרוחב מהווה בסיס לאלגוריתמים רבים שפועלים על גרפים, בהם [[אלגוריתם דייקסטרה]] ו[[האלגוריתם של פרים]].