|
|
עמוד:277
נניח שקדקוד המקור הוא = 1 י . 1 קל לראות שבעזרת האלגוריתם שתואר לעיל לא נגיע לעולם לקדקודים שמספרם 5 , 4 . 7-ו להלן האלגוריתם למציאת עץ פורש DFS ( נסמנו ב- , ( 7 תוך כדי סריקת קדקודי הגרף וקביעת סדר התיוג של הקדקודים . האלגוריתם נכון לגרף קשיר ולגרף לא קשיר , לגרף מכוון ולגרף לא מכוון . DFS ( G ) = 0 . 1 קבוצה" ) 7 ריקה (* *) בהתחלה עץ פורש - ריק (* / < - 1 . 2 . 3 לכל קדקוד v בצע : Usedfv ] < - FALSE . 4 סוף הלולאה . . 5 כל עוד קיים הקדקוד , Ve v שעבורו Used [ v ] = FALSE אזי בצע : קרא לשגרה Search _ DFS ( v ) . 6 סוף הלולאה . ולהלן השגרה הרקורסיבית שכותרתה : Search _ DFS ( v ) 1 Used [ v ] < - TRUE . 1 C [ v ] < - / . 2 /< - / + 1 . 3 A לכל קדקוד w שהוא שכן של קדקוד v בצע ו 4 . 1 אם ? Used ( w ) = FALSE אז בצע :
|
|