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