Implementation (Part 1)
الدرس 5 من 9 في دورة البحث بالعمق أولاً - خوارزميات المخططات على Coddy.
سنقوم ببناء خوارزمية البحث بالعمق أولاً (DFS) بدءاً من البحث في قائمة المجاورة.
التحدي
سهلقبل التنقل في رسم بياني (graph)، نحتاج إلى معرفة جيران كل رأس (vertex). لنقم ببناء عملية البحث هذه من قائمة الحواف (edges) المسطحة.
اكتب دالة باسم getNeighbors تأخذ مصفوفة edges (أزواج مسطحة [u0, v0, u1, v1, ...]، غير موجهة) ورأسًا node، وتعيد قائمة مرتبة لجيران node، بدون تكرار.
على سبيل المثال، getNeighbors([0,1, 0,2, 1,2, 3,0], 0) تعيد [1, 2, 3].
جرّب بنفسك
#include <stdlib.h>
int* getNeighbors(int* edges, int edges_size, int node, int* returnSize) {
// اكتب الكود هنا
*returnSize = 0;
return edges;
}
اختبر نفسكيتضمن هذا الدرس اختبارًا قصيرًا. ابدأ الدرس للإجابة عليه وتتبّع تقدمك.
جميع دروس البحث بالعمق أولاً - خوارزميات المخططات
2The Algorithm
How it works?Pseudo CodeImplementation (Part 1)Implementation (Part 2)
Time and Space Complexity