אלגוריתמי חיפוש בגרפים
חקרו אלגוריתמי סריקת גרפים ומסלולים קצרים ביותר
אלגוריתמי חיפוש בגרפים מיושמים בניווט GPS, רשתות חברתיות, ניתוח תלויות ועוד. BFS מוצא את המסלול הקצר ביותר במספר צלעות וטוב לגרפים לא ממושקלים. DFS חוקר לעומק ומשמש לזיהוי מחזורים ומיון טופולוגי. אלגוריתם דייקסטרה מוצא מסלול קצר ביותר בגרף ממושקל עם משקלים חיוביים. A* מוסיף היוריסטיקה לדייקסטרה לחיפוש יעיל יותר כשיש מידע מרחבי.
🔍 מה קורה עכשיו?
לחצו על הפעל או שלב כדי להתחיל את האלגוריתם.
1 / 0
פסאודו-קוד
חיפוש לרוחב (BFS)
איך זה עובד
חוקר את כל השכנים בעומק הנוכחי לפני שעובר לצמתים בעומק הבא. משתמש במבנה נתונים תור (FIFO).
💡 הרעיון המרכזי
חקרו שכבה אחר שכבה, כמו אדוות המתפשטות מאבן שנזרקה למים.
סיבוכיות
O(V + E)
O(V)
מתי להשתמש
מציאת מסלול קצר ביותר בגרפים לא ממושקלים, סריקה לפי רמות, בדיקת קישוריות.
🎓 קוויז לימודי - חיפוש לרוחב (BFS)
ציון: 0 / 5באיזה מבנה נתונים משתמש BFS לניהול הצמתים שיש לבקר?
מדריך לאלגוריתמי חיפוש בגרפים
חיפוש בגרפים — הבסיס לניווט, רשתות ותכנון מסלולים
גרף הוא אוסף של צמתים (קדקודים) והקשתות המחברות ביניהם. זהו המודל הטבעי לכל דבר שמורכב מישויות ומקשרים: רשתות כבישים, קשרי חברות ברשת חברתית, תלויות בין משימות, מצבים אפשריים במשחק, או דפי אינטרנט וקישורים ביניהם. אלגוריתמי חיפוש בגרפים הם הכלים שמאפשרים לענות על שאלות כמו האם קיים מסלול, מהו המסלול הקצר ביותר, ואילו צמתים ניתן להגיע אליהם.
כל אלגוריתמי החיפוש חולקים מבנה משותף: מחזיקים אוסף של צמתים שגילינו אך טרם חקרנו (החזית), שולפים ממנו צומת, מסמנים אותו כמבוקר, ומוסיפים את שכניו שטרם נראו. ההבדל היחיד — והמכריע — בין האלגוריתמים הוא הסדר שבו שולפים מהחזית. בחירת מבנה הנתונים הזה היא שקובעת אם נקבל חיפוש לרוחב, חיפוש לעומק או דייקסטרה.
בוויזואליזציה שלמעלה הצבעים מסמנים את מצב כל צומת: צומת התחלה, צומת יעד, צמתים בחזית שממתינים לעיבוד, צמתים שכבר בוקרו, והצומת הנבדק כרגע. בסיום החיפוש מודגש המסלול שנמצא, כך שאפשר לראות ישירות איך הבחירה בסדר העיבוד משנה את התוצאה.
חיפוש לרוחב (BFS) מול חיפוש לעומק (DFS)
חיפוש לרוחב מחזיק את החזית בתור (FIFO) ולכן חוקר את הגרף בשכבות: קודם כל השכנים הישירים של צומת ההתחלה, אחר כך כל השכנים שלהם, וכן הלאה. התוצאה החשובה היא שברגע שחיפוש לרוחב מגיע לצומת כלשהו, הוא הגיע אליו במספר הקשתות המינימלי. לכן הוא פותר מסלול קצר ביותר בגרף לא משוקלל, וזה בדיוק מה שהופך אותו לבחירה הנכונה למבוכים, לרשתות חברתיות ולחישוב דרגות הפרדה.
חיפוש לעומק מחזיק את החזית במחסנית (LIFO) — או פשוט משתמש ברקורסיה — ולכן צולל עמוק ככל האפשר לאורך ענף אחד לפני שהוא חוזר אחורה. הוא אינו מבטיח מסלול קצר ביותר, אבל הוא הכלי הנכון לשאלות מבניות: זיהוי מעגלים, מציאת רכיבי קשירות, מיון טופולוגי, ומציאת גשרים ונקודות חיתוך.
מבחינת משאבים שניהם O(V+E) בזמן. בזיכרון חיפוש לרוחב מחזיק שכבה שלמה בבת אחת, שיכולה להיות רחבה מאוד בגרפים מסועפים, בעוד חיפוש לעומק מחזיק רק את המסלול הנוכחי — לכל היותר עומק הגרף. בגרף רחב ורדוד חיפוש לעומק חסכוני יותר; בגרף עמוק וצר חיפוש לרוחב עדיף, ומימוש רקורסיבי של חיפוש לעומק עלול אף לגלוש מהמחסנית.
אלגוריתם דייקסטרה וחיפוש A* — מסלולים בגרף משוקלל
כשלקשתות יש משקלים — מרחק, זמן נסיעה, עלות — חיפוש לרוחב כבר אינו נכון, כיוון שמסלול עם מעט קשתות עשוי להיות יקר ממסלול עם קשתות רבות וזולות. אלגוריתם דייקסטרה פותר זאת בכך שהוא מחליף את התור בתור עדיפויות ושולף תמיד את הצומת בעל המרחק המצטבר הקטן ביותר שטרם טופל. עם ערימה בינארית הסיבוכיות היא O((V+E) log V).
התנאי ההכרחי לדייקסטרה הוא שכל המשקלים אי-שליליים. הסיבה נעוצה בהנחת היסוד שלו: ברגע ששולפים צומת מהתור, המרחק אליו סופי ולא ישתפר. קשת שלילית מאוחרת יותר עלולה להפריך זאת. לגרפים עם משקלים שליליים משתמשים באלגוריתם בלמן-פורד, שאיטי יותר עם O(V·E) אך גם מזהה מעגלים שליליים.
חיפוש A* מרחיב את דייקסטרה בעזרת פונקציית היוריסטיקה שמעריכה את המרחק הנותר ליעד. במקום לשלוף לפי המרחק שנצבר בלבד, הוא שולף לפי הסכום של המרחק שנצבר וההערכה שנותרה. כשההיוריסטיקה קבילה — כלומר לעולם אינה מעריכה יתר על המידה — החיפוש מובטח למצוא את המסלול האופטימלי, אך מבקר בהרבה פחות צמתים מדייקסטרה. זהו האלגוריתם שמאחורי ניווט GPS ומציאת דרך במשחקי מחשב, בדרך כלל עם מרחק אוקלידי או מרחק מנהטן כהיוריסטיקה.
שאלות נפוצות
מה ההבדל בין BFS ל-DFS?
חיפוש לרוחב (BFS) משתמש בתור וחוקר את הגרף שכבה אחר שכבה, ולכן מוצא תמיד את המסלול עם מספר הקשתות הקטן ביותר בגרף לא משוקלל. חיפוש לעומק (DFS) משתמש במחסנית או ברקורסיה וצולל עמוק לאורך ענף אחד לפני חזרה אחורה, ולכן אינו מבטיח מסלול קצר ביותר. שניהם O(V+E) בזמן, אך חיפוש לרוחב צורך יותר זיכרון בגרפים רחבים וחיפוש לעומק בגרפים עמוקים.
מתי משתמשים ב-BFS ומתי ב-DFS?
השתמשו בחיפוש לרוחב כשצריך מסלול קצר ביותר בגרף לא משוקלל, לחישוב מרחקים מצומת מקור, או לחיפוש בשכבות כמו דרגות הפרדה ברשת חברתית. השתמשו בחיפוש לעומק לשאלות מבניות: זיהוי מעגלים, מציאת רכיבי קשירות, מיון טופולוגי, בעיות נסיגה ופתרון חידות שדורשות חקירת כל האפשרויות.
איך עובד אלגוריתם דייקסטרה?
דייקסטרה מוצא את המסלול הזול ביותר מצומת מקור לכל שאר הצמתים בגרף עם משקלים אי-שליליים. הוא מחזיק תור עדיפויות ושולף בכל צעד את הצומת עם המרחק המצטבר הקטן ביותר שטרם טופל, ואז מעדכן את המרחקים לשכניו אם נמצא מסלול זול יותר. הסיבוכיות עם ערימה בינארית היא O((V+E) log V).
למה דייקסטרה לא עובד עם משקלים שליליים?
דייקסטרה מניח שברגע ששולפים צומת מתור העדיפויות, המרחק אליו סופי ולא ישתפר עוד. קשת בעלת משקל שלילי יכולה להפריך הנחה זו — מסלול ארוך יותר עשוי להסתיים בקשת שלילית ולהיות זול יותר בסך הכול. במקרים כאלה משתמשים באלגוריתם בלמן-פורד, שסיבוכיותו O(V·E) אך תומך במשקלים שליליים ומזהה מעגלים שליליים.
מה ההבדל בין דייקסטרה לחיפוש A*?
דייקסטרה מתקדם לפי המרחק שנצבר מנקודת ההתחלה בלבד ולכן מתפשט לכל הכיוונים באופן שווה. חיפוש A* מוסיף פונקציית היוריסטיקה שמעריכה את המרחק הנותר ליעד, ובוחר לפי סכום שני הערכים — מה שמכוון את החיפוש לעבר היעד ומצמצם דרמטית את מספר הצמתים שנבדקים. כשההיוריסטיקה קבילה, שני האלגוריתמים מוצאים את אותו מסלול אופטימלי, אך A* מגיע אליו מהר יותר.
מהי סיבוכיות הזמן של חיפוש בגרפים?
חיפוש לרוחב וחיפוש לעומק רצים ב-O(V+E), כאשר V הוא מספר הצמתים ו-E מספר הקשתות, כיוון שכל צומת וכל קשת נבדקים פעם אחת. דייקסטרה עם ערימה בינארית רץ ב-O((V+E) log V), ועם ערימת פיבונאצי ב-O(E + V log V). חיפוש A* במקרה הגרוע זהה לדייקסטרה, אך בפועל מהיר בהרבה כשההיוריסטיקה איכותית.