Implementation (Part 2)
الدرس 6 من 9 في دورة البحث بالعرض أولاً - خوارزميات المخططات على Coddy.
الآن نقوم بعبور الرسم البياني في طبقات باستخدام طابور.
التحدي
متوسطالآن قم ببناء عملية المرور الكاملة.
اكتب دالة باسم bfs تأخذ n، ومصفوفة edges المسطحة (غير موجهة)، ورأس start، وتعيد الترتيب الذي يزور به BFS الرؤوس بدءاً من start.
قم ببناء قائمة التجاور (مع ترتيب الجيران تصاعدياً)، ثم استخدم طابوراً (queue): قم بتمييز وإضافة نقطة البداية إلى الطابور، ثم قم بشكل متكرر بسحب رأس من الطابور، وتسجيله، وإضافة جيرانه غير المزارين إلى الطابور.
يتم زيارة الرؤوس التي يمكن الوصول إليها من start فقط.
جرّب بنفسك
#include <stdlib.h>
int* bfs(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