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