38. البحث بعمق أولاً (Depth First Search - DFS)

DFS هي خوارزمية اجتياز للرسوم البيانية تستكشف أبعد ما يمكن على طول كل فرع قبل التراجع (backtracking).

المفهوم: التغلغل بعمق

تخيل التنقل في متاهة. DFS يشبه النزول في مسار واحد حتى تصل إلى طريق مسدود، ثم العودة (التراجع) وتجربة المسار التالي المتاح.

يستخدم DFS عادةً مكدس (Stack) (أو العودية، التي تستخدم مكدس الاستدعاءات) لتذكر العُقد التي يجب زيارتها بعد ذلك.

خطوات الخوارزمية (العودية)

1. البدء من عُقدة مصدر S.
2. وضع علامة على S كمُزارة.
3. لكل جار V لـ S:
   • إذا لم يتم زيارة V، فاستدعِ DFS بشكل عودي على V.

حالات الاستخدام

• إيجاد المكونات المتصلة.
• اكتشاف الدورات في رسم بياني.
• الفرز الطوبولوجي.