البحث بالعمق أولاً (DFS)
ادخل متاهة، وواصل السير حتى تصل إلى طريق مسدود، ثم ارجع إلى آخر مفترق وجرّب الطريق التالي. هكذا يستكشف البحث بالعمق أولاً الرسم البياني. إنه من أبسط خوارزميات الرسوم البيانية، والمكدس الذي يحتفظ به يخبرك بأكثر مما قد تتوقع.
الفكرة
الرسم البياني مجموعة من العقد تربط بينها حواف: غرف وأبواب، وصفحات ويب وروابط، ومهام والمهام التي تعتمد عليها. يزور البحث بالعمق أولاً كل عقدة يمكنه بلوغها من البداية، لكن بترتيب معيّن: يواصل دائمًا من العقدة التي بلغها مؤخرًا. ويحتفظ بمكدس للعقد التي هو داخلها. توضع العقدة الجديدة في القمة، ولا تُرفع عقدة إلا بعد استكشاف كل ما حولها.
خطوة بخطوة
ضع البداية في المكدس وأعطها رقم الزيارة 1. انظر إلى الجار التالي للعقدة التي في القمة. إن لم يُرَ من قبل، فأعطه رقم الزيارة التالي، وتذكّر العقدة التي بُلغ منها، وضعه في قمة المكدس. وإن رُئي من قبل، فتجاوزه. وحين لا يبقى للعقدة التي في القمة جيران لفحصها، تكون قد انتهت: ارفعها وواصل مع العقدة التي تحتها. توقف حين يصبح المكدس فارغًا، أو حين يُبلغ الهدف.
مثال
خذ رسمًا بيانيًا حوافه A–B وA–C وB–D وC–D وC–E وD–F، وابدأ من A، وافحص الجيران بالترتيب الأبجدي. من A ينتقل البحث إلى B، ومن B إلى D، ومن D إلى C، ومن C إلى E، فيكون المكدس A, B, D, C, E. وفي الطريق ترى C العقدة A، وهي ما زالت في المكدس: الحافة C–A تُغلق الدورة A, B, D, C. ليس لدى E شيء جديد، فتنتهي، ثم C، ويتراجع البحث إلى D، التي ما زال لديها F. ترتيب الزيارة هو A, B, D, C, E, F. وإذا كانت E هي الهدف، يتوقف DFS عند المسار A → B → D → C → E، أي أربع حواف، مع أن A → C → E يحتاج إلى حافتين فقط.
فيمَ يفيد
المكدس دائمًا مسار من البداية إلى العقدة الحالية، مما يجعل DFS مناسبًا بطبيعته للمتاهات والألغاز: هذه هي فكرة التراجع. في رسم بياني غير موجّه، الحافة إلى عقدة ما زالت في المكدس تُغلق دورة. وفي رسم بياني موجّه، يعطي سرد العقد بعكس ترتيب انتهائها ترتيبًا طوبولوجيًا، فتأتي كل مهمة بعد المهام التي تعتمد عليها. ويجد البحث بالعمق أولاً أيضًا المكونات المتصلة والجسور ونقاط التمفصل، ونسخته العشوائية طريقة كلاسيكية لتوليد المتاهات.
التاريخ
في القرن التاسع عشر وصف عالم الرياضيات الفرنسي شارل بيير تريمو طريقة للخروج من أي متاهة بوضع علامات على الممرات، وهي بحث بالعمق أولاً يُنفَّذ بالطباشير. وفي عامي 1972 و1973 بيّن روبرت تارجان وجون هوبكروفت أن DFS يحل كثيرًا من مسائل الرسوم البيانية في زمن خطي، من المكونات المتصلة بقوة إلى اختبار إمكانية رسم الرسم البياني دون تقاطعات. ونالا جائزة تورينغ لعام 1986 جزئيًا بفضل هذا العمل.
جرّبه
افتح التطبيق واضغط «خطوة». تُظلَّل العقدة التي تُفحص جيرانها، وتكون العقد التي في المكدس زرقاء، والعقد المنتهية خضراء، وعلى كل منها رقم زيارتها. ويظهر المكدس أسفل الرسم البياني، من البداية حتى العقدة التي في القمة. راقب سطر الحالة لترى الحواف التي تُغلق دورة، واختر هدفًا لترى كم قد يطول المسار الذي يجده مقارنة بالبحث بالعرض أولاً.
الأسئلة المتداولة
ما التعقيد الزمني لـ DFS؟
O(V + E) لعدد V من العقد (الرؤوس) وE من الحواف: تدخل كل عقدة المكدس وتخرج منه مرة واحدة، وتُفحص كل حافة من طرفيها. ويحتاج إلى ذاكرة إضافية O(V) للمكدس والعلامات.
لماذا يستخدم DFS مكدسًا؟
لأن مبدأ «آخر من يدخل أول من يخرج» يجعل البحث يواصل من أحدث عقدة ويتراجع إلى التي قبلها. والعودية تفعل الشيء نفسه بمكدس الاستدعاءات في البرنامج. ولو استُخدم طابور بدلاً منه، لانتشر البحث حلقة بعد حلقة: وهذا هو البحث بالعرض أولاً.
هل يمثل DFS العودي مشكلة في الرسوم البيانية الكبيرة؟
قد يكون كذلك: المسار الطويل يعني عودية عميقة، وكثير من اللغات تحدّ عمق الاستدعاءات. والمكدس الصريح داخل حلقة تكرار يتجنب هذا الحد مع زيارة العقد بالترتيب نفسه.
أين يُستخدم DFS؟
في حل المتاهات والألغاز بالتراجع، وإيجاد الدورات، وترتيب المهام حسب اعتمادياتها (الترتيب الطوبولوجي)، وإيجاد المكونات المتصلة والمتصلة بقوة، وتوليد المتاهات، وفي المترجمات وأدوات البناء التي تجتاز رسوم الاعتماديات.
هل أنت مستعد لتجربتها؟
افتح PictorX في متصفحك - بدون تثبيت، ولا يلزم وجود بطاقة ائتمان للبدء.
جرّب البحث بالعمق أولاً