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