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

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

פסאדו קוד

1. Color every vertx in BLUE

2. time=0

3. for each vertex u in G

4.      if u is BLUE

5.                 DFS-VISIT(u)

6. end

 

DFS-Visit(u)

1. color u in GRAY

2. d[u]=time=time+1

3. for each vertex v adj. to u

4.      if v is BLUE

5.              DFS-VISIT(v)

6. color u in GREEN

7. f[u]=time=time+1

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

האלגוריתם מתחיל באיתחול כל הקודקודים (שורה 1) ואז עובר על כל הקודקודים לפי סדר כלשהו (במקרה שלנו - בחרנו סדר לקסיקוגרפי) ועבור כל אחד שעוד לא נתגלה מפעיל את הפונקציה DFS-VISIT. (שורות 2-6).

תיאור הפונקציה DFS-VISIT:

הפונקציה מתחילה בצביעת הקודקוד בו היא מטפלת באפור, ונותנת לו את זמן הגילוי (שורות 1-2), אח"כ מתפנה הפונקציה לעבור על כל שכניו (לפי סדר לקסיקוגרפי) שעוד לא התגלו ומפעילה עליהם את הפונקציה DFS-VISIT.

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

דוגמת הרצה

ניתוח זמן ריצה

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

במהלך בדיקה על קודקוד נריץ שוב את הבדיקה על כל שכניו, מאחר וסכום כל השכנים של כל הקודקודים הוא (O(E העלות הכוללת של כל בדיקות הקודקודים היא (O(E.

זמן הריצה הכולל של חיפוש לעומק הוא (O(E+V.