Motivation
الدرس 2 من 9 في دورة البحث بالعمق أولاً - خوارزميات المخططات على Coddy.
يستكشف DFS الرسم البياني من خلال الالتزام بمسار واتباعه إلى أقصى حد ممكن، ثم التراجع (backtracking) إلى آخر رأس (vertex) يحتوي على جار غير مستكشف.
لماذا نتعلم DFS؟
- أساسي: فهو يشكل الأساس لاكتشاف الدورات (cycle detection)، والفرز الطوبولوجي (topological sorting)، والمكونات المتصلة (connected components)، والعديد من الخوارزميات الأخرى.
- بسيط وغير مكلف: يعمل في زمن قدره O(V + E) باستخدام مكدس (stack) (أو الاستدعاء الذاتي recursion) وعلامة للمواقع التي تمت زيارتها (visited marker).
- متعدد الاستخدامات: نفس عملية المرور تجيب على أسئلة مثل "هل هذان الرأسان متصلان؟" و"كم عدد الأجزاء المنفصلة في الرسم البياني؟"
للحفاظ على نتائج متوقعة، نقوم دائمًا بزيارة جيران الرأس بترتيب تصاعدي.
جرّب بنفسك
لا يتضمّن هذا الدرس تحدّيًا برمجيًا.
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
