DFS
الدرس 11 من 14 في دورة المخططات - سلسلة هياكل البيانات #9 على Coddy.
ينتقل البحث بالعمق أولاً (Depth-First Search) إلى العمق قبل التوسع عرضياً. بدءاً من رأس (vertex) معين، فإنه يتبع حافة واحدة إلى أقصى حد ممكن، ثم يتراجع (backtracks) ويجرب الحافة التالية. تستخدم النسخة التكرارية مكدساً (stack): يتم سحب (pop) رأس، وتسجيله، ثم دفع (push) جيرانه غير المزارين إليه مرة أخرى.
لجعل DFS ينتج ترتيب اجتياز محدد (deterministic) في هذا التحدي، قم بدفع الجيران بترتيب عكسي (reverse-sorted). بهذه الطريقة، يستقر الجار الأصغر في أعلى المكدس ويتم معالجته أولاً، مما يطابق الترتيب الذي سينتجه DFS العودي (recursive) عبر الجيران بترتيب تصاعدي.
انتبه من دفع الرأس مرتين (يمكن لجيران مختلفين أن يمتلكوا نفس الرأس). تحقق من مجموعة العناصر التي تمت زيارتها (visited set) في بداية الحلقة التكرارية وتخطَّ الرأس إذا تمت زيارته بالفعل.
التحدي
سهلاكتب دالة dfs تستقبل مصفوفة ثنائية الأبعاد من الأعداد الصحيحة adjacency (كل صف يمثل حافة [u, v]) وعددًا صحيحًا start، وتعيد ترتيب زيارة DFS بدءًا من start كقائمة من الأعداد الصحيحة.
قم ببناء الرسم البياني (graph) عن طريق إضافة كل حافة. استخدم خوارزمية DFS التكرارية باستخدام مكدس (stack): قم بسحب رأس (vertex)، وإذا لم تتم زيارته، فقم بتسجيله ودفع جيرانه بترتيب فرز عكسي بحيث يتمت معالجة الأصغر أولاً.
يجب عليك استخدام فئة Graph (المتوفرة في graph) - لا تستخدم الأدوات المدمجة في اللغة (maps، sets) لتمثيل التجاور (adjacency). يمكن استخدام أنواع المكتبة القياسية (stdlib) للبيانات المساعدة للخوارزمية (visited sets، stacks).
جرّب بنفسك
#include <stdio.h>
#include "solution.h"
int main() {
int n, m, start;
if (scanf("%d %d %d", &n, &m, &start) != 3) return 0;
int adjacency[1024][2];
for (int i = 0; i < m; i++) scanf("%d %d", &adjacency[i][0], &adjacency[i][1]);
int out[MAX_VERTICES];
int outn = dfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}