ההבדל בין BFS ו- DFS ההבדל בין
רוחב ראשון חיפוש (הידוע גם בשם BFS) היא שיטת חיפוש המשמש להרחיב את כל הצמתים של גרף מסוים. זה מבצע משימה זו על ידי חיפוש בכל פתרון יחיד כדי לבחון ולהרחיב את הצמתים (או שילוב של רצפים בהם). ככזה, BFS אינו משתמש באלגוריתם היוריסטי (או באלגוריתם המחפש פתרון באמצעות מספר תרחישים). לאחר כל הצמתים מתקבלים, הם מתווספים בתור הידוע בתור הראשון, תור ראשון. צמתים אלה שלא נחקרו מאוחסנים במכולה המסומנת 'פתוחה'; לאחר שנחקרו הם מועברים למיכל המסומן "סגור".
עומק ראשון חיפוש (הידוע גם בשם DFS) היא שיטת חיפוש המחפר עמוק יותר לתוך הצומת של הילד של החיפוש עד המטרה היא הגיעה (או עד שיש צומת ללא כל תמורות אחרות או " יְלָדִים'). לאחר מציאת מטרה אחת, החיפוש אחורה אל הצומת הקודם שהלך עם פתרון, חוזר על התהליך עד שכל הצמתים נבדקו בהצלחה. ככזה, צמתים ממשיכים לשים בצד לחקירה נוספת - זה נקרא יישום רקורסיבי.
התכונות של BFS הן מורכבות בחלל ובזמן, השלמות, הוכחת השלמות והאופטימיות. מורכבות החלל מתייחסת לחלק היחסי של מספר הצמתים ברמה העמוקה ביותר של חיפוש. מורכבות הזמן מתייחסת לכמות בפועל של 'זמן' המשמשת לבחינת כל נתיב שצומת ייקח בחיפוש. השלמות היא, למעשה, חיפוש הממצא פתרון בתרשים, ללא תלות בסוג הגרף. ההוכחה לשלמות היא הרמה הרדוד ביותר שבה המטרה נמצאת בצומת בעומק מוגדר. לבסוף, אופטימליות מתייחס BFS שאינו משוקלל - כלומר גרף המשמש עלות יחידה צעד.
DFS הוא הפלט הטבעי ביותר באמצעות עץ פורש - שהוא עץ המורכב מכל קודקודים וכמה קצוות בתרשים לא מכוונת. במבנה זה, הגרף מחולק לשלושה סוגים: קדימה קצוות, הצבעה מן הצומת אל הצומת ילד; הגב, מצביע אל הצומת קודמת; ואת קצוות לחצות, אשר לא עושים אף אחד מאלה.
סיכום:
1. A BFS מחפש כל פתרון יחיד בגרף כדי להרחיב את הצמתים שלו; DFS מאורה עמוק בתוך הצומת ילד עד המטרה היא הגיעה.
2. התכונות של BFS הן מורכבות של מרחב וזמן, שלמות, הוכחת השלמות והאופטימיות; הפלט הטבעי ביותר עבור DFS הוא עץ פורש עם שלושה סוגים: קצוות קדמיים, קצוות אחוריים וקצוות חוצים.
