|
|
עמוד:263
בתום ביצוע האלגוריתם , תמונת המצב היא : תוך כדי סריקת קדקודי הגרף , G = ( V , E ) נוצר תת-גרף G = ( V \ F ) כאשר E היא קבוצת הקשתות שעברנו דרכן בכדי לסרוק את קדקודי הגרף בשיטת BFS קשתות אלו מסומנות ומודגשות . G הוא עץ המכיל את כל הקדקודים הנגישים מקדקוד המקור . ( 5 ) בהמשך נראה כי לכל צומת v נגיש , 5-מ אורך המסלול הקצר ביותר * c < 5-מ נמצא בעץ הזה . העץ הפורש ( BFS ) של הגרף שפירטנו בדוגמה הוא : עץ פורש BFS
|
|