|
|
עמוד:269
גם בשיטה זו , בדומה לשיטת הסריקה , BFS נשתמש במערך הבוליאני Used כך ש- Used [ v ] יציין אם ביקרנו בקדקוד v או לאו . ברור שבתחילת האלגוריתם לכל קדקוד v בגרף נציב את הערך FALSE ל- , Usedfv ] כיוון שבתחילת האלגוריתם עדיין לא ביקרנו בקדקודי הגרף . לגבי כל קדקוד האלגוריתם חייב לשמור מידע על זהות הקדקוד הקודם לו בסריקה . לפיכך , נשתמש במערך , P כך ] -ש ע ] / > ייצג הקדקוד שממנו הגענו \ -ל בעת הסריקה . כמו כן , רצוי , אף כי הדבר אינו הכרחי , למספר את קדקודי הגרף לפי סדר הביקורים בהם ( הנקרא גם תיוג . ( לקדקוד הראשון שבו נבקר נצמיד "תג , " 1 לקדקוד השני שבו נבקר נצמיד '' תג , " 2 וכן הלאה . לאור זאת , נשתמש במערך בשם C ( המציין , ( count - כך C [ v ] -v יציין את המספור שניתן לקדקוד v בגרף בעת הסריקה . להלן האלגוריתם לשיטת הס 1 יקה לעומק ( DFS ) לגרף לא מכוון : צעד / ?& - 0 : 0 v ) v < - 1 מכיל קדקוד מקור ) צעד : 1 לכל קדקוד v בגרף פרט לקדקוד המקור *) , Used [ v ] < - FALSE בתחילת האלגוריתם עדיין לא ביקרנו בקדקודי הגרף (* *) , Usedfl ] < r- TRUE מאחר שהסריקה מתחילה מקדקוד . (* 1 צעד *) C [ v ] < - / /< - / + ! . ? 2 מספור של הקדקוד . (* v
|
|