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