BFS
الدرس 10 من 14 في دورة المخططات - سلسلة هياكل البيانات #9 على Coddy.
تم تصميم التحديات التالية لاستخدام فئة Graph التي قمت ببنائها للتو.
يرسل لك كل تحدٍ ملف graph مغلقاً (وهو Graph النهائي من الفصل السابق) وملف solution جديداً حيث تكتب دالة تستخدم الـ Graph.
خوارزميتنا الأولى: Breadth-First Search. بدءاً من رأس (vertex)، يزور BFS جميع الرؤوس التي يمكن الوصول إليها في موجات: أولاً البداية، ثم كل شيء يبعد حافة واحدة، ثم كل شيء يبعد حافتين، وهكذا. يستخدم التنفيذ الكلاسيكي طابوراً (queue): قم بإدراج البداية (enqueue)، ثم قم بالإخراج من الطابور (dequeue) بشكل متكرر، وسجل الرأس كـ "تمت زيارته"، وقم بإدراج أي جيران غير مزارين في الطابور.
نظراً لأن قوائم الجيران ليس لها ترتيب ثابت، يمكن لعمليتي تشغيل BFS صحيحتين أن تنتجا أوامر اجتياز مختلفة. لجعل الإجابة حتمية في هذا التحدي، قم بفرز جيران كل رأس تصاعدياً قبل إدراجهم في الطابور.
التحدي
سهلاكتب دالة bfs تستقبل مصفوفة ثنائية الأبعاد من الأعداد الصحيحة adjacency (كل صف يمثل حافة [u, v]) وعددًا صحيحًا start، وتعيد ترتيب زيارة BFS من start كقائمة من الأعداد الصحيحة.
قم ببناء الرسم البياني: لكل [u, v] في adjacency، استدعِ g.addEdge(u, v). ثم ابدأ عملية BFS من start باستخدام طابور (queue). عند معالجة جيران رأس ما، قم بفرزهم تصاعديًا لضمان أن يكون المخرج محددًا (deterministic).
يجب عليك استخدام فئة Graph (المتوفرة في graph) - لا تستخدم الأدوات المدمجة في اللغة (maps، sets) لتمثيل التجاور. يمكن استخدام أنواع المكتبة القياسية (stdlib) للبيانات المساعدة للخوارزمية (مجموعات العقد التي تمت زيارتها، الطوابير).
جرّب بنفسك
#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 = bfs(adjacency, m, start, out);
for (int i = 0; i < outn; i++) {
if (i > 0) printf(" ");
printf("%d", out[i]);
}
printf("\n");
return 0;
}