Time and Space Complexity

تعقيد الوقت:

• O(V + E)
  • بناء قائمة التجاور يمر على كل حافة مرة واحدة، وعملية المرور تزور كل رأس وتنظر في كل حافة عدداً ثابتاً من المرات.

تعقيد المساحة:

• O(V + E)
  • تخزن قائمة التجاور كل حافة، ومصفوفة الزيارة والمكدس يتسع كل منهما لما يصل إلى V من الرؤوس.

ملخص:

• يستكشف DFS بعمق أولاً، ويتراجع عندما تنفد الجيران غير المزارة.
• يعمل في وقت خطي وهو العمود الفقري للعديد من خوارزميات الرسوم البيانية.