Implementation (Part 2)
الدرس 6 من 9 في دورة البحث بالعمق أولاً - خوارزميات المخططات على Coddy.
الآن نقوم بالمرور عبر المخطط بالكامل باستخدام مكدس (stack).
التحدي
متوسطالآن قم ببناء المسار الكامل.
اكتب دالة باسم dfs تأخذ n، ومصفوفة edges المسطحة (غير موجهة)، ورأس start، وتعيد الترتيب الذي يزور به DFS الرؤوس، بدءاً من start.
أولاً، قم ببناء قائمة الجوار (رتب جيران كل رأس تصاعدياً). ثم قم بتشغيل DFS تكراري باستخدام مكدس (stack). يتم زيارة الرؤوس التي يمكن الوصول إليها من start فقط.
لزيارة الجيران بترتيب تصاعدي، قم بدفعهم إلى المكدس من الأكبر إلى الأصغر.
جرّب بنفسك
#include <stdlib.h>
int* dfs(int n, int* edges, int edges_size, int start, int* returnSize) {
// اكتب الكود هنا
*returnSize = 0;
return edges;
}
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
جميع دروس البحث بالعمق أولاً - خوارزميات المخططات
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity