|
|
صفحة: 279
קיבלנו יער . כאמור , סדר התיוג אינו בהכרח יחיד , ולכן גס היער שנקבל אינו בהכרח יחיד . ניתוח היעילות של אלגוריתם הסריקה לעומק ( DFS ) כידוע , סכום האורכים של רשימות הסמיכות , המייצגת את הגרף , G = ( V , E ) הוא ? 0 (\ E \) הלולאות שבשורות 3 5-ו של השגרה DFS מתבצעות בזמן , 0 (| V |) לא כולל הזמן הנדרש לביצוע הקריאה לשגרה . Search _ DFS ( v ) השגרה Search _ DFS נקראת בדיוק פעם אחת עבור כל קדקוד . v € V הלולאה המרכזית של Search _ DFS ( v ) מתבצעת כסכום האורכים של רשימות הסמיכות , ולכן השגרה Search _ DFS ( v ) מתבצעת בזמן ? 0 (\ E \) לפיכך , סיבוביות זמן הריצה של האלגוריתם DFS היא . O (| V | + | E |) - סריקת עץ נבצע את תהליך הסריקה על העץ הזה :
|
|