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

ראשי > אלגורתמים בסיסים בתורת הגרפים > סריקה > חיפוש לעומק, חלק שלישי

חיפוש לעומק - חלק שלישי

תכונות של חיפוש-לעומק

חיפוש-לעומק מניב מידע רב על מבנה הגרף, ניתן להשתמש באלג' לסווג את קשתות הגרף.
נגדיר ארבעה סוגים של קשתות:

1. קשתות עץ - קשת (u,v) היא קשת עץ אם v התגלה לראשונה ע"י בדיקת הקשת (u,v).
2. קשתות אחורה - כל הקשתות (u,v) המחברות קדקוד u לקודקוד קדמון v שקדם לו בעץ העומק.
לולאות עצמיות, שעשויות להופיע בגרפים מכוונים, נחשבות גם הן לקשתות אחורה.
3. קשתות קדימה - כל הקשתות (u,v) אשר מחברות קודקוד u לצאצא v בעץ עומק אשר הן אינן קשתות עץ.
4. קשתות חוצות - אלו הן כל הקשתות האחרות, עשויות לקשר בין קודקודים בעצי עומק שונים או בין קודקודים באותו עץ עומק אשר קודקוד אחד נוא לא צאצא של השני.

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

כיצד לסווג קשתות לפי DFS

בזמן ריצת DFS האלגוריתם נותן לכל קודקוד, כאמור, את דרגת הכניסה ואת דרגת היציאה.

אנו יכולים להשתמש בדרגות אלו, על מנת לחלק את קשתות הגרף בהתאם לחלוקה שציינו בראש העמוד. נניח וקיימת קשת בין u ל-v נשתמש בערכי הגילוי והסיום של הקודקודים בהתאם לטבלה הבאה:

u->v	קשת עץ	קשת קדמית	קשת אחורית	קשת חוצה
גילוי (d)	d[u] < d[v]	d[u] < d[v]	d[u] > d[v]	d[u] > d[v]
סיום (f)	f[u] > f[v]	f[u] > f[v]	f[u] < f[v]	f[u] > f[v]