ما معنى DFS Forest؟ شرح غابة البحث بالعمق في الخوارزميات وهياكل البيانات
غابة البحث بالعمق (DFS Forest) هي ببساطة مجموعة أشجار البحث بالعمق (DFS Trees) التي نحصل عليها عندما نُشغِّل خوارزمية البحث بالعمق على رسم بياني كامل. إذا كان الرسم متصلاً وبدأنا من عقدة واحدة، تنتج شجرة واحدة فقط. أما إذا كان الرسم مؤلفًا من أجزاء منفصلة، أو كان موجّهًا ولا يمكن الوصول إلى كل عقده من نقطة بداية واحدة، فإننا نُعيد تشغيل البحث من كل عقدة لم تُزَر بعد، فينتج عن ذلك عدة أشجار مستقلة. هذه المجموعة من الأشجار مجتمعةً هي ما نسميه «غابة DFS».
بعبارة أدق: الشجرة الواحدة تُغطّي العقد التي وصلنا إليها انطلاقًا من جذر واحد، والغابة تُغطّي الرسم البياني بأكمله عبر عدة جذور.
ما هي شجرة DFS أولاً؟
قبل الغابة يجب أن نفهم الشجرة. عند تطبيق البحث بالعمق نبدأ من عقدة، ثم نتوغّل في العمق عبر أحد فروعها حتى نصل إلى النهاية، ثم نتراجع (backtrack) ونجرّب فرعًا آخر. الحواف التي نعبرها فعليًا للوصول إلى عقدة جديدة لم تُكتشف بعد تُسمى حواف الشجرة (Tree Edges)، وهي التي تُشكّل شكل شجرة DFS.
كل عقدة تُسجَّل لها قيمتان مهمتان أثناء العمل: زمن الاكتشاف (متى دخلناها لأول مرة) وزمن الانتهاء (متى فرغنا من كل ما تحتها). هاتان القيمتان أساس معظم التطبيقات المتقدمة.
متى تتحوّل الشجرة إلى غابة؟
الغابة تظهر تحديدًا عندما لا تكفي شجرة واحدة لتغطية كل العقد:
- ابدأ بأي عقدة غير مُكتشَفة وطبّق عليها DFS بالكامل؛ فتنمو شجرة أولى.
- عند انتهاء كل العقد المتصلة بها، ابحث عن عقدة أخرى ما زالت غير مُكتشَفة.
- ابدأ منها بحثًا جديدًا؛ فتنمو شجرة ثانية.
- كرّر هذه الخطوة حتى لا تبقى عقدة واحدة غير مُكتشَفة.
النتيجة: عدة أشجار = غابة DFS. وفي الرسم غير الموجَّه، عدد أشجار الغابة يساوي بالضبط عدد المكوّنات المتصلة في الرسم، وهذه خاصية عملية جدًا لكشف الأجزاء المنفصلة.
أنواع الحواف داخل غابة DFS
عند تصنيف حواف الرسم بالنسبة إلى الغابة نحصل على أربعة أنواع:
- حواف الشجرة (Tree Edges): تقود إلى عقدة جديدة لأول مرة.
- الحواف الخلفية (Back Edges): تعود إلى سلَف (عقدة أعلى في نفس المسار)، ووجودها دليل على وجود دورة (cycle).
- الحواف الأمامية (Forward Edges): تصل من عقدة إلى حفيد لها اكتُشِف مسبقًا عبر مسار آخر.
- الحواف العابرة (Cross Edges): تربط عقدتين لا تنتمي إحداهما لسلالة الأخرى.
ملاحظة دقيقة يغفلها كثيرون: في الرسم غير الموجَّه لا وجود للحواف الأمامية ولا العابرة إطلاقًا؛ لا تظهر سوى حواف الشجرة والحواف الخلفية فقط. أما الأنواع الأربعة مجتمعةً فلا تظهر إلا في الرسوم الموجَّهة.
غير موجَّه أم موجَّه؟ الفرق في الغابة
| المعيار | رسم غير موجَّه | رسم موجَّه |
|---|---|---|
| أنواع الحواف الممكنة | شجرة + خلفية فقط | الأنواع الأربعة كاملة |
| عدد أشجار الغابة | يساوي عدد المكوّنات المتصلة | يعتمد على ترتيب البدء ولا يساوي عدد المكوّنات بالضرورة |
| كشف الدورة | أي حافة خلفية = دورة | حافة خلفية = دورة |
| أبرز استخدام | كشف المكوّنات المتصلة | الترتيب الطوبولوجي والمكوّنات القوية |
النقطة الجوهرية: شكل الغابة في الرسم الموجَّه ليس ثابتًا؛ فتغيير ترتيب زيارة العقد قد يُنتج غابة مختلفة تمامًا، وهذا طبيعي وليس خطأً.
أين تُستخدم غابة DFS عمليًا؟
المفهوم ليس نظريًا فحسب، بل يقف خلف خوارزميات يومية:
- كشف المكوّنات المتصلة في الشبكات (كل شجرة = مكوّن).
- كشف الدورات عبر رصد الحواف الخلفية.
- الترتيب الطوبولوجي لجدولة المهام المترابطة اعتمادًا على أزمنة الانتهاء.
- إيجاد المكوّنات المتصلة بقوة (SCC) عبر خوارزميتَي Tarjan وKosaraju.
- تحديد نقاط التمفصل والجسور في الشبكات لمعرفة نقاط الضعف فيها.
خطأ شائع يجب تجنّبه
الخلط الأكثر شيوعًا هو الظن بأن عدد أشجار الغابة في الرسم الموجَّه يساوي عدد مكوّناته. هذا صحيح فقط في الرسوم غير الموجَّهة. في الموجَّه، قد تنشأ عدة أشجار داخل مكوّن واحد أو العكس، حسب نقطة الانطلاق. كما يخطئ البعض بإهمال إعادة تشغيل البحث من العقد غير المُكتشَفة، فيحصلون على شجرة ناقصة بدل غابة كاملة تُغطّي كل الرسم.
الأسئلة الشائعة
هل غابة DFS مفهوم مختلف عن شجرة DFS؟ هما مرتبطان: الشجرة نتيجة بحث واحد من جذر واحد، والغابة مجموع كل الأشجار الناتجة عن تغطية الرسم بأكمله. الشجرة الواحدة هي حالة خاصة من الغابة عندما يكفي جذر واحد.
كيف أعرف عدد الأشجار في الغابة بسرعة؟ عُدّ كم مرة استدعيت البحث من عقدة جديدة غير مُكتشَفة في الحلقة الرئيسية؛ هذا العدد هو عدد الأشجار. وفي الرسم غير الموجَّه يساوي عدد المكوّنات المتصلة.
ما الفرق بينها وبين BFS؟ البحث بالعرض (BFS) يستكشف العقد مستوىً مستوى، وينتج شجرة/غابة أيضًا لكن بحواف مختلفة (لا وجود لحواف أمامية فيها). أما DFS فيتوغّل في العمق أولًا، وهو الأنسب لكشف الدورات والترتيب الطوبولوجي.
ما تعقيد بناء غابة DFS؟ تعقيدها الزمني هو O(V + E)، أي متناسب مع عدد العقد (V) وعدد الحواف (E)، وهو الأمثل لأننا نمرّ على كل عقدة وكل حافة مرة واحدة.