البحث بالعمق أولًا (DFS)
يستكشف المخطط باتباع طريق واحد إلى أعمق ما يمكن، ثم يعود إلى آخر مفترق. المكدس الظاهر على الشاشة هو هذا الطريق.
- O(V + E)
- الذاكرة O(V)
- مكدس
V و E: عدد الرؤوس وعدد الحواف. تعني O(V + E) أن كل رأس وكل حافة يُعالَجان عددًا ثابتًا من المرات.
المكدس: الداخل أخيرًا يخرج أولًا. يتابع DFS دائمًا من آخر رأس وصل إليه.
مصطلحات أخرى في هذه الصفحة
- الرأس: نقطة في المخطط، مرسومة هنا كدائرة فيها حرف.
- الحافة: خط يصل بين رأسين. يمكنك هنا السير عليه في الاتجاهين.
- الجيران: الرؤوس المتصلة برأس ما عبر حافة. تُفحص بالترتيب الأبجدي.
جرّب هذا: اختر المخطط الذي فيه دورات. كل حافة متقطعة تعود إلى رأس موجود على المكدس أو انتهى: هذه الحافة تُغلق دورة.
كيف يعمل
يستدعي DFS نفسه على أول جار لم يره بعد، ثم على أول جار جديد لذلك الرأس، وهكذا. وعندما لا يبقى لرأس جيران جدد، ينتهي استدعاؤه ويعود DFS خطوة واحدة ليجرّب الجار التالي هناك. تشكّل الاستدعاءات المفتوحة مكدسًا، وهو دائمًا الطريق من البداية إلى الرأس الحالي. الرقم بجانب الرأس هو ترتيب زيارته.
متى يكون خيارًا جيدًا
استخدم DFS لمعرفة ما يمكن الوصول إليه أصلًا، أو لإيجاد الدورات، أو للسير في متاهة، أو لترتيب مهام يعتمد بعضها على بعض. لكنه لا يجد أقصر طريق.