40. البحث بعمق مقابل البحث بعرض: اختيار الاجتياز الصحيح
يتمتع كل من DFS و BFS بنفس التعقيد الزمني التقاربي، O(V + E) عند استخدام قائمة تجاور (Adjacency List)، ولكنهما يحلان مشاكل مختلفة بشكل أفضل.
| الميزة | DFS (البحث بعمق أولاً) | BFS (البحث بعرض أولاً) |
|---|---|---|
| هيكل البيانات | مكدس (Stack) (أو العودية) | قائمة انتظار (Queue) |
| نمط البحث | عميق، يستنفد مساراً واحداً أولاً | واسع، يستكشف طبقة تلو الأخرى |
| التعقيد الزمني | O(V + E) | O(V + E) |
| التعقيد المكاني | O(H) حيث H هو ارتفاع الرسم البياني | O(B) حيث B هو أقصى عرض/عدد العُقد في مستوى واحد |
| الأفضل لـ | اكتشاف الدورات، الفرز الطوبولوجي، استكشاف الهياكل الكبيرة والعميقة (إذا كان الهدف على الأرجح عميقاً). | العثور على أقصر المسارات (غير الموزونة)، إيجاد المكونات المتصلة، الاستكشاف الضحل (إذا كان الهدف على الأرجح قريباً من البداية). |