מוטיבציה

DFS סורק גרף בכך שהוא בוחר מסלול ומתקדם בו עד כמה שאפשר, ואז חוזר לאחור אל הקודקוד האחרון שיש לו שכן שטרם נחקר.

למה ללמוד DFS?

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

כדי שהתוצאות יהיו צפויות, אנחנו תמיד מבקרים בשכנים של קודקוד בסדר עולה.