הצגת המקור של הדף "אלגוריתם חיפוש לעומק"

[[קובץ:Depth-first-tree.svg|200px|שמאל|ממוזער|עץ חיפוש לעומק, כולל סדר סריקת הקודקודים בחיפוש.]]
ב[[מדעי המחשב]], '''אלגוריתם חיפוש לעומק''' (ב[[אנגלית]]: '''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 הוא שורש. במקרה זה האלגוריתם בודק אם קיים צומת שעדיין לא ביקר, ואם יש כזה הוא מגדיר אותו כשורש וחוזר על התהליך עד שכל הצמתים בוקרו.

מימוש פשוט ויעיל של החיפוש הוא על ידי [[מחסנית (מבנה נתונים)|מחסנית]]. גילוי צומת מתבטא בהכנסתו לראש המחסנית ונסיגה מצומת מתבטאת בהוצאתו מראש המחסנית.

[[סיבוכיות מקום|סיבוכיות המקום]] של האלגוריתם היא, במקרה הגרוע, <math>\ O(d)</math> כאשר d הוא אורך המסלול הפשוט המקסימלי בגרף, וסיבוכיות הזמן היא O(m), כאשר m מספר הקשתות בגרף.

==שימושים== 

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

אלגוריתם זה נמצא בשימוש ב[[אופטימיזציה הרמונית]].

==פסאודו קוד - מימוש על ידי מחסנית==
[[קובץ:פסאודו קוד חיפוש לעומק.jpg|ממוזער]]
'''DFS – מימוש על ידי מחסנית'''

המימוש ממספר את הצמתים על פי הסדר בו התגלו,

[[קלט]]: גרף G=(V,E), מכוון או לא מכוון

[[פלט]]: יער DFS של G וגם לכל צומת v זמן הגילוי של v.

סימון: k[v] זמן הגילוי של ''v'', ו-p[v] – האב של ''v'' ביער ה-DFS.
{{-}}
<div dir="ltr" class="mw-content-ltr">


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);
</div>
הגרף המכוון ''F''=(''V,E''<nowiki/>') שנוצר על ידי הרצת האלגוריתם הוא הגרף המורכב מהקשתות (''p''(''u''),''u''). כעת נוכיח מספר תכונות של האלגוריתם, ובמיוחד שגרף זה הוא יער מכוון המכיל את כל צמתי הגרף.



== ראו גם ==
*[[אלגוריתם חיפוש לרוחב]]
*[[אלגוריתם חיפוש A*]]

==קישורים חיצוניים==
{{ויקישיתוף בשורה}}
* {{MathWorld}}

[[קטגוריה:אלגוריתמים בתורת הגרפים|חיפוש לעומק]]
[[קטגוריה:אלגוריתמי חיפוש|עומק]]