סיבוכיות זמן ומקום

סיבוכיות זמן:

• O(V + E)
  • בניית רשימת השכנות נוגעת בכל קשת פעם אחת, והמעבר מבקר בכל קודקוד ובודק כל קשת מספר קבוע של פעמים.

סיבוכיות מקום:

• O(V + E)
  • רשימת השכנות מאחסנת כל קשת, ומערך הביקורים והמחסנית מכילים כל אחד עד V קודקודים.

סיכום:

• DFS חוקר לעומק תחילה, וחוזר לאחור כשנגמרים השכנים שטרם בוקרו.
• הוא פועל בזמן ליניארי ומהווה את הבסיס לאלגוריתמים רבים על גרפים.