אני יודע שאחד זה חיפוש לעומק והשני חיפוש לרוחב. השאלה היא מה ההבדל מבחינת יעילות, באיזה מקרים משתמשים בכל אחד מהאלגוריתמים?
תודה רבה על העזרה.
אלוגריתם BFS - חיפוש לרוחב סורק את הגרף בצורה שמבטיחה שכל צומת שנמצא באותו רכיב קשירות של הצומת ההתחלתי ייבדק, וסריקה זו נעשית בזמן אופטימלי, הליניארי למספר הקשתות והצמתים בגרף. לכן, חיפוש לרוחב מהווה בסיס לאלגוריתמים רבים שפועלים על גרפים (לדוגמא: אלגוריתם דייקסטרה, פריים אלגוריתם ואלגוריתם אדמונדס-קארפ).
אלוגריתם DFS - האלגוריתם מתחיל את החיפוש מצומת שרירותי בגרף ומתקדם לאורך הגרף עד אשר הוא נתקע, לאחר מכן הוא חוזר על עקבותיו עד שהוא יכול לבחור להתקדם לצומת אליו טרם הגיע.
(כמו סריקת מבוך)
ניתן להשתמש באלגוריתם חיפוש לעומק בתור בסיס לאלגוריתמים רבים שפועלים על גרפים. (לדוגמא: מציאת רכיבים קשירים היטב בגרף, מציאת מסלולי אוילר, מעגלים בגרף או מיון טופולוגי).
בשורה התחתונה, BFS מתאים לחיפוש קודקודים שקרובים למקור לעומת DFS שמתאים לקודקודים המרוחקים מהמוצא.
על מנת לחפש ב DFS נשתמש במחסנית לעומת BFS שהגיוני יותר להשתמש בתור.
מבחינת סיבוכיות חישוב כמובן שזהה O(V+E).