|
|
עמוד:256
לקדקוד מקור בגרף אין הורה ( לכן הוא המקור , ( ולכן נבצע את ההשמה . P [ v ] = $ מאחר שהסריקה מתחילה מקדקוד המקור , S אז הקדקוד S מתגלה מיד , ולכן יש לבצע את ההשמה : . Used [ S ] < - TRUE צעד 3 כאמור , תפקידו של תור ( 0 לנהל את השכבות ולקבוע בכל שלב , / לכל > 0 ן , מהם הקדקודים ששייכים לשכבה / -ה ית . ברור כי לשכבה 0 שייך אך ורק צומת המקור . 5 לכן נבצע את ההשמה . Q ?& - { S } ? . בשלב הזה התור Q מכיל קבוצת קדקודים השייכים לשכבה . 0 הערה : בתור Q נמצאים קדקודים אשר נתגלו ( ביקרנו בהם תוך כדי סריקה , ( אך רשימת הסמיכות ( שכנים ) שלהם טרם נתגלתה . צעד 4 נסתכל על הקדקוד שבחזית התור Q ונכנה אותו בשם . v עתה נבחן את כל השכנים של הקדקוד . v לכל קדקוד , w שהנו שכן של הקדקוד v ושעדיין לא נתגלה , נבצע את הצעדים שלהלן : . 1 נבקר בו כעת ; ( Usedfw ] < - TRUE ) . 2 אורך המסלול ^ -מ ™ -ל שווה לאורך המסלול 5-מ ל-ע ועוד אחת ( עקב המעבר על הקשת ; (( v , w ) . 3 יש לזכור שהקדקוד v חינו הורה של הקדקוד ? , w . 4 נצרף את הקדקוד w לתור . Q לאחר שנבחנו כל הקדקודים השכנים של , v נסיר מהתור Q את הקדקוד v כיוון שהטיפול בו הסתיים . כך חוזר התהליך על עצמו עד שמטפלים בכל הקדקודים שניתן להגיע אליהם 5-מ ( קדקוד המקור . ( ברגע שהתור Q יתרוקן , יסתיים האלגוריתם , כיוון שכל הקדקודים שנשיגים 5-מ נתגלו ( וטופלו . ( נדגים את צעדי האלגוריתם שתואר לעיל על הגרף שלהלן ו
|
|