עמוד:264

טענה : תת-הגרף G = { V , E ) מגדיר עץ T אשר ייקרא העץ הפורש של שיטת הסריקה לרוחב ( בקיצור-עץ פורש . ( BFS הטענה נכונה , כיוון שקל לראות כי | F | ( . newer והגרף 6 " הוא גרף קשיר , ולכן , לפי משפט , 5 . 3 . 1 . 2 הגרף G' הוא עץ . ניתוח היעילות של אלגוריתם הסריקה לרוהב ( BFS ) לפני שנבדוק את היעילות של האלגוריתם הנדון , ניזכר כי אם G הוא גרף מכוון , והוא מיוצג באמצעות רשימות סמיכות , אזי סכום האורכים של כל רשימות הסמיכות הוא . \ E \ ואם הגרף G לא מכוון , והוא מיוצג באמצעות רשימות סמיכות , אזי סכום האורכים של כל רשימות הסמיכות הוא . 2 | £ | מכאן - סכום האורכים של רשימת הסמיכות הוא . 0 (| £ |) צעד 1 דורש זמן , 0 (\ V \) כיוון שסורקים את כל קדקודי הגרף . צעד 2 דורש זמן , 0 (| 1 |) כיוון שיש גישה ישירה לאינדקס במערך . צעד 3 דורש זמן , 0 {\\\) כיוון שזוהי פעולה של הכנסת איבר לתור . צעד 4 הפעולות על התור ( התייחסות לאיבר שבחזית התור והסרת איבר מהתור ) דורשות זמן . 0 {\\\) כל קדקוד נכנס לתור פעם אחת לכל היותר ולכן גם יוצא ממנו פעם אחת לכל היותר . מכאן , הזמן הנדרש לפעולות על התור הוא . 0 ( 1 ^ 1 ) רשימת הסמיכות של כל קדקוד v נסרקת רק כאשר מסירים את הקדקוד v מן התור , וברור מתוך האלגוריתם שרשימת הסמיכות של כל קדקוד v נסרקת פעם אחת לכל היותר . סכום האורכים של רשימות הסמיכות הוא , O (\ E \) לכן הזמן הכולל הנדרש עבור סריקת רשימות הסמיכות הוא לכל היותר . 0 (| £ |) מכאן י

מטח : המרכז לטכנולוגיה חינוכית


לצפייה מיטבית ורציפה בכותר