אלגוריתם חיפוש לעומק

במדעי המחשב, אלגוריתם חיפוש לעומק (Depth-first search, DFS) הוא שיטה לעבור על גרף. גרף הוא מבנה של נקודות (צמתים) שמחוברות בקשרים (קשתות). האלגוריתם פועל גם על גרפים מכוונים וגם על גרפים בלתי מכוונים.

באופן אינטואיטיבי מתחילים מצומת כלשהו. בכל צעד עוברים לצומת שכן שלא ביקרו בו עדיין. אם אין שכן כזה, האלגוריתם נסוג אחורה עד שמוצא צומת עם שכן לא מבוקר. התהליך דומה לסריקה שיטתית של מבוך. במהלך הריצה בנוי עץ חיפוש מכוון: לכל צומת שאינו השורש נכנסת קשת מהצומת שגילה אותו. בתכונה חשובה בגרף בלתי מכוון, כל קשת בגרף מחברת צומת עם צאצא שלו בעץ החיפוש. לדוגמה, בקונפיגורציה מסוימת לא תיתכן קשת בין צומת 2 ו-7 אם אף אחד מהם אינו צאצא של השני, אבל קשת בין 2 ל-5 אפשרית אם 5 הוא צאצא של 2.


האלגוריתם מתחיל בצומת שנקרא שורש. בכל שלב בודקים אם לצומת הנוכחי יש שכן שלא בוקר. אם יש, עוברים לשכן הזה ואומרים שהצומת הנוכחי גילה את השכן. אם כל השכנים כבר בוקרו, חוזרים אחורה לצומת שגילה את הצומת הנוכחי. אם הגענו לשורש ואין עוד שכנים לא מבוקרים, בודקים אם קיימים צמתים שלא בוקרו; אם כן בוחרים אחד מהם כשורש חדש וממשיכים, עד שכל הצמתים בוקרו.

מימוש פשוט ויעיל נעשה באמצעות מחסנית. מחסנית (stack) היא מבנה שבו מכניסים פריט לראש ומוצאים אותו משם, כך הגילוי מיוצג בהכנסה והנסיגה בהוצאה.

כמויות משאבים: הזיכרון שהאלגוריתם צריך תלוי באורך המסלול הפשוט הארוך ביותר בגרף. הזמן שתופס הריצה תלוי במספר הקשתות בגרף.


DFS משמש כבסיס לאלגוריתמים רבים על גרפים. בין השימושים המרכזיים: מציאת צמתי הפרדה (articulation points) ורכיבים אי-פריקים (biconnected components) בגרף בלתי מכוון; מציאת רכיבים קשירים היטב (strongly connected components) בגרף מכוון; מציאת מסלולים אוילריים ומעגלים; ומיון טופולוגי. האלגוריתם גם מופיע בהקשרים של אופטימיזציה הרמונית.


המימוש המקובל ממספר את הצמתים לפי זמן הגילוי ושומר עבור כל צומת את האב ביער ה-DFS. ראשית מאתחלים לכל צומת זמן גילוי אפס ואב=nil. אחר כך, כל עוד יש צומת שלא בוקר, בוחרים אותו כנקודת התחלה, מכניסים אותו למחסנית ומסמנים זמן גילוי. בעוד המחסנית לא ריקה בוחרים את הצומת בראש המחסנית (u). אם קיים שכן v של u שעדיין לא בוקר, מגדירים את v כגילוי חדש, שומרים את u כאב של v ומדחפים את v למחסנית. אם אין שכן כזה, מוציאים את u מהמחסנית. בסיום נוצר גרף מכוון F שמורכב מקשתות (p(u),u). גרף זה הוא יער מכוון שמכיל את כל צמתי הגרף.

אלגוריתם חיפוש לעומק (DFS) הוא דרך לבדוק גרף. גרף הוא קבוצת נקודות שמחוברת בקווים.

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

התוצאה היא עץ שמראה מי גילה את מי. בעץ כזה, בכל קו שמחבר שתי נקודות, אחת מהן היא 'הורה' והשנייה היא 'ילד'. לכן לא כל צמד נקודות יכול להיות מחובר אם הן לא קשורות כהורה וילד.

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

כמה דברים חשובים: הזיכרון שצריך קשור לאורך המסלול הארוך ביותר בגרף. משך הזמן תלוי בכמה קווים (קשתות) יש בגרף.


1. אתחול: מסמנים שכל הצמתים לא בוקרו.
2. בוחרים צומת שלא בוקר, מסמנים אותו ובודקים אותו.
3. כל פעם שעוברים לצומת חדש מסמנים אותו ושומרים מי האב שלו.
4. אם אין עוד שכנים, חוזרים אחורה במחסנית.
5. ממשיכים עד שכל הצמתים בוקרו.


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