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

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