אלגוריתם חיפוש לרוחב
מתוך ויקיפדיה, האנציקלופדיה החופשית
במדעי המחשב, אלגוריתם חיפוש לרוחב הוא אלגוריתם המשמש למעבר על צומתי גרף, לרוב תוך חיפוש צומת המקיים תכונה מסוימת. הוא מתחיל מצומת שרירותית שמכונה "הצומת ההתחלתית", ועובר על כל צמתי הגרף כך שבתחילה הוא עובר על הצמתים שמרחקם מהצומת ההתחלתית הוא קשת אחת, אחר כך אלו שמרחקם הוא שתי קשתות, וכן הלאה, ומכאן שמו (כי הוא מחפש לרוחב הגרף ולא לעומקו).
חיפוש לרוחב סורק את הגרף בצורה שמבטיחה שכל צומת שנמצא באותו רכיב קשירות של הצומת ההתחלתי ייבדק, וסריקה זו נעשית בזמן אופטימלי, הלינארי למספר הקשתות והצמתים בגרף. בשל כך, חיפוש לרוחב מהווה בסיס לאלגוריתמים רבים שפועלים על גרפים, ביניהם אלגוריתם דייקסטרה והאלגוריתם של פרים.
[עריכה] תיאור אינטואיטיבי
האלגוריתם משתמש בתור רגיל כדי לדעת מהו הצומת הבא בו הוא עומד לבקר. בכל פעם שבה הוא מבקר בצומת הוא מסמן אותו ככזה שנבדק, ואז בודק את כל הקשתות שיוצאות ממנו. אם קשת מובילה לצומת שטרם נבדק, צומת זה מוסף לתור. בדרך זו מובטח כי האלגוריתם יסרוק את הצמתים בסדר שנקבע על פי מרחקם מהצומת ההתחלתי (כי צומת שנכנס לתור יצא ממנו רק לאחר שכל הצמתים שהיו בו קודם יצאו).
[עריכה] תיאור פורמלי
קטע הקוד הבא הוא ויקי-קוד, פסאודו-קוד מוצע לשימוש במאמרים רבים.
function breadthFirstSearch (Start, Goal) {
push(Queue,Start)
while notEmpty(Queue)) {
Node := pop(Queue)
if Node = Goal {
return Node
}
for each Child in Expand(Node) {
if notVisited(Child) {
setVisited(Child)
push(Queue, Child)
}
}
}
}

