חיפוש לעומק - חלק ראשון
בדפים הבאים נעסוק
באלגוריתם חיפוש לעומק, באנגלית הוא נקרא Depth-First-Search
(או בקצרה - DFS).
כפי
שמרמז שמו, האסטרטגיה הננקטת באלג' זה היא לחפש "עמוק"
יותר בגרף ככל שאפשר.
באלג'
זה נבדקות הקשתות היצאות מן הקודקוד שהתגלה אחרון שעדיין
יש לו קשתות יוצאות שטרם נבדקו (נסמן את קודקוד זה ב-v).
לאחר
שנבדקו כל הקשתות היוצאות מ-v
החיפוש "נסוג" וממשיך בבדיקת הקשתות היוצאוצ מהקודקוד
שממנו התגלה v.
תהליך
זה נמשך עד שמתגלים כל הקודקודים האפשריים מקודקוד המקור
הראשון, אם נותרו בגדף קודקודים שטרם התגלו, אחד מהם נבחר
להיות קודקוד מקור חדש, והאלג' מתבצע שוב מהמקור החדש.
התהליך חוזר על עצמו עד אשר מתגלים כל קודקודי הגרף.
כמו בחיפוש-לרוחב,
נזכור את כל הקודקוד הקודם של כל קודקוד. (הקודקוד הקודם
של v זה הקודקוד u
שכאשר סרקנו את שכניו של u
גילינו את הקודקוד v).
שלא כמו בחיפוש-לרוחב,
תת-גרף הקודמים הנוצר ע"י חיפוש-לעומק עשוי להיות מורכב
מכמה עצים ולא עץ אחד בלבד ולכן נקרא לו יער-עומק המורכב
ממספר עצי-עומק. (הדבר עשוי לקרות מכיוון שחיפוש-לעומק יכול
להתנהל ממספר מקורות).
כמו
בחיפוש-לרוחב, במהלך האלג' נצבעים הקודקודים כדי לציין
את מצבם. כל הקודקודים נצבעים תחילה בלבן, קודקוד נצבע באפור
כאשר הוא מתגלה לראשונה בחיפוש ונצבע בשחור כאשר מסתיימת
הבדיקה של כל שכניו (רשימת הסמיכויות שלו
נבדקה במלואה).
בנוסף ליצירת יער-עומק,
חיפוש-עומק שומר לכל קודקוד
v שתי חותמות זמן,
אחת (תסומן ב d[v])
מציינת מתי התגלה v
לראשונה, כלומר מתי נצבע v
באפור, השניה )תסומן
ב f[d])
מציינת מתי סוימה הבדיקה של כל שכניו של v,
כלומר מתי v
נצבע בשחור.
חותמות זמן אלה משמשות
באלג' גרפים רבים ומסייעות בניתוח מבנה הגרף.
בעמוד הבא נציג את האלגוריתם
לסריקת עומק וכן הסבר על הפסאדו-קוד. בעמוד שאחריו ניגע
בנושאים נוספים הקשורים לסריקה זו וכן ננתח תכונות נוספות
שלה.
