אלגוריתם חיפוש לעומק
במדעי המחשב, אלגוריתם חיפוש לעומק (באנגלית: Depth-first search, ראשי תיבות: DFS) הוא אלגוריתם המשמש למעבר על גרף או לחיפוש בו. האלגוריתם מוגדר עבור גרפים בלתי מכוונים ועבור גרפים מכוונים.
אינטואיטיבית, האלגוריתם מתחיל את החיפוש מצומת שרירותי בגרף, ובכל צעד מתקדם מהצומת בו הוא נמצא לצומת שכן שעוד לא ביקר בו, אם יש כזה. אם ביקר בכל הצמתים השכנים, הוא חוזר על עקבותיו עד שהוא מגיע לצומת שיש לו שכן שטרם ביקר בו. דרך פעולת האלגוריתם דומה במידת מה לסריקה שיטתית של מבוך. האלגוריתם מחזיר עץ מכוון שבו לכל צומת שאינו שורש נכנסת קשת מהצומת שגילה אותו. במיוחד כל קשת בעץ החיפוש לעומק היא גם קשת בגרף עליו נעשה החיפוש. התכונה המאפיינת עץ חיפוש לעומק בגרף לא מכוון, שהיא הסיבה לשימושיות שלו, היא שכל קשת בגרף עליו נעשה החיפוש מחברת צומת עם צאצא שלו בעץ החיפוש. להמחשה: בגרף שעץ החיפוש לעומק שלו מופיע בציור, לא תיתכן קשת בין צומת 2 לצומת 7, מפני ש אף אחד מצמתים אלו אינו צאצא של השני. אך תיתכן קשת בין צומת 2 לצומת 5, מפני ש-5 צאצא (נכד) של 2.
תיאור האלגוריתם
עריכהאלגוריתם חיפוש לעומק מתחיל בצומת כלשהו, שייקרא שורש (צומת 1 בציור המצורף). בכל שלב האלגוריתם בודק אם לצומת בו הוא נמצא כרגע, נסמנו u, יש צומת שכן, נסמנו v, שהאלגוריתם עדייין לא ביקר בו. אם יש שכן v כזה האלגוריתם עובר מu לv ואומרים שu גילה את v (בציור צומת 2 גילה את הצמתים 3 ו6). אם כל השכנים של הצומת u כבר בוקרו, האלגוריתם נסוג לצומת ממנו התגלה u. אם אין צומת שגילה את u חייב להתקיים ש u הוא שורש. במקרה זה האלגוריתם בודק אם קיים צומת שעדיין לא ביקר, ואם יש כזה הוא מגדיר אותו כשורש וחוזר על התהליך עד שכל הצמתים בוקרו.
מימוש פשוט ויעיל של החיפוש הוא על ידי מחסנית. גילוי צומת מתבטא בהכנסתו לראש המחסנית ונסיגה מצומת מתבטאת בהוצאתו מראש המחסנית.
סיבוכיות המקום של האלגוריתם היא, במקרה הגרוע, כאשר d הוא אורך המסלול הפשוט המקסימלי בגרף, וסיבוכיות הזמן היא O(m), כאשר m מספר הקשתות בגרף.
שימושים
עריכהאלגוריתם חיפוש לעומק הוא בסיס לאלגוריתמים רבים שפועלים על גרפים. למשל, מציאת צמתי הפרדה ורכיבים אי-פריקים בגרף לא מכוון, מציאת רכיבים קשירים היטב בגרף מכוון, מציאת מסלול אוילרי ומעגלים בגרף או מיון טופולוגי שלו.
אלגוריתם זה נמצא בשימוש באופטימיזציה הרמונית.
פסאודו קוד - מימוש על ידי מחסנית
עריכה
DFS – מימוש על ידי מחסנית
המימוש ממספר את הצמתים על פי הסדר בו התגלו,
קלט: גרף G=(V,E), מכוון או לא מכוון
פלט: יער DFS של G וגם לכל צומת v זמן הגילוי של v.
סימון: k[v] זמן הגילוי של v, ו- p[v] – האב של v ביער ה DFS.
for all v in V: k[v] := 0 ; p[v] := nil;
i:= 0;
while there is a vertex s with k[s] = 0
STACK := [s]; i := i+1; k[s] := i;
While STACK ≠ ∅
u:= head(STACK); {u is the "center of activity"}
if there is an edge (u,v) s.t. k[v]=0
i:= i+1; k[v]:= i; p[v] := u ;
push(STACK,v);
else
pop(STACK);
הגרף המכוון F=(V,E') שנוצר על ידי הרצת האלגוריתם הוא הגרף המורכב מהקשתות (p(u),u). כעת נוכיח מספר תכונות של האלגוריתם, ובמיוחד שגרף זה הוא יער מכוון המכיל את כל צמתי הגרף.
ראו גם
עריכהקישורים חיצוניים
עריכה
- אלגוריתם חיפוש לעומק, באתר MathWorld (באנגלית)