يشرح هذا الدليل Depth-First Search (DFS) من الصفر وبأسلوب عملي. الهدف هو فهم المشكلة التي تحلها الخوارزمية، سبب عملها، طريقة تنفيذها، ومتى تظهر في أنظمة البرمجيات الحقيقية.
ما المشكلة التي تحلها؟
يشرح هذا الدليل Depth-First Search (DFS) من الصفر وبأسلوب عملي. الهدف هو فهم المشكلة التي تحلها الخوارزمية، سبب عملها، طريقة تنفيذها، ومتى تظهر في أنظمة البرمجيات الحقيقية.
الفكرة الأساسية ببساطة
تعتمد الخوارزمية على تمثيل المشكلة كرسم بياني ثم معالجة العقد والحواف وفق قاعدة محددة للوصول إلى النتيجة المطلوبة.
خطوات التنفيذ
- حدد معنى العقد والحواف في المشكلة.
- اختر تمثيل الرسم البياني المناسب.
- تتبّع الحالة المطلوبة مثل visited أو distance أو degree.
- اختبر النتيجة والحالات الحدّية قبل الاستخدام الفعلي.
مثال JavaScript
function dfs(graph, start) {
const seen = new Set(), order = [];
function visit(u) {
if (seen.has(u)) return;
seen.add(u); order.push(u);
for (const v of graph[u] ?? []) visit(v);
}
visit(start); return order;
}أمثلة عملية من العالم الحقيقي
- تحليل العلاقات بين المستخدمين والخدمات
- إدارة الاعتماديات بين الوحدات البرمجية
- الشبكات والاتصالات
- المسارات والعمليات داخل أنظمة الأعمال
التعقيد الزمني والذاكري
O(V + E) زمان و O(V) حافظه
متى نستخدمها؟
استخدمها عندما تتوافق بنية المشكلة مع الهدف الذي صممت له هذه الخوارزمية.
متى لا تكون مناسبة؟
لا تستخدمها تلقائياً إذا تغير نوع الرسم أو الهدف؛ قد تكون خوارزمية أخرى أبسط أو أسرع.
الخلاصة
لا تختَر الخوارزمية بالاسم فقط. حدّد أولاً هل الرسم موجه أم غير موجه، موزون أم غير موزون، وهل الهدف هو traversal أو reachability أو shortest path أو connectivity أو spanning structure أو optimization.