|
|
עמוד:258
מקדקוד 1 לקדקוד 7 הוא . 1 בנוסף , ברור כי ההורה של הקדקודים 4 7-ו הוא הקדקוד 1 וברור כי Used [ 4 ] = Used [ 7 ] = TRUE שכן כעת הם נתגלו . בטבלה שלהלן מוצגת תמונת המצב המתקבלת : הקדקודים 4 7-ו מתווספים לתור , Q ולכן . 2 = { 1 , 4 , 7 } מאחר שהטיפול בקדקוד 1 הסתיים , נוציא אותו מהתור , Q ולכן . Q = { 4 , 7 ) התהליך ממשיך וחוזרים לצעד . 4 צעד 4 ( איטרציה ( 2 v < -4 4 . 1 4 . 2 השכנים של v הם הקודקדים 1 6-ו ( בעזרת המערך Used רואים כי כבר ביקרנו בקדקוד c אך עדיין לא בקדקוד , 6 ולכן נבקר אך ורק בקדקוד . ( 6 אורך המסלול מקדקוד 1 לקדקוד 4 הוא , 1 ומקדקוד 4 לקדקוד 6 הוא , 1 לכן אורך המסלול מקדקוד 1 לקדקוד 6 הוא . 2 ברור כי ההורה של הקדקוד 6 הוא קדקוד , 4 ובנוסף , ברור כי Used [ 6 ] = True כי כעת מבקרים בקדקוד . 6 לפיכך , תמונת המצב היא ! כעת , קדקוד 6 מתווסף לתור , Q לכן . Q = { 4 , 7 , 6 } שימו לב שבתור Q קדקודים השייכים לשכבה 1 ( הקדקודים 4 ( 7-ו וקדקודים השייכים לשכבה 2 ( הקדקוד . ( 6 מאחר שהטיפול בקדקוד 4 הסתיים , נוציא אותו מהתור Q ולכן : . 2 = { 7 , 6 } ניתן לתאר את תמונת המצב המתקבלת בטבלה בעזרת התרשים שלהלן :
|
|