BFS
שיעור 10 מתוך 14 בקורס גרפים – סדרת מבני נתונים מס' 9 של Coddy.
האתגרים הבאים נועדו להשתמש במחלקה Graph שבנית זה עתה.
כל אתגר מגיע עם קובץ graph נעול (הקובץ הסופי Graph מהפרק הקודם) וקובץ solution חדש שבו תכתוב פונקציה שמשתמשת ב-Graph.
האלגוריתם הראשון שלנו: חיפוש לרוחב. החל מקודקוד, BFS מבקר בכל הקודקודים הנגישים בגלים: תחילה בקודקוד ההתחלה, אחר כך בכל הקודקודים במרחק קשת אחת, לאחר מכן בכל הקודקודים במרחק שתי קשתות, וכן הלאה. המימוש הקלאסי משתמש בתור: מכניסים את קודקוד ההתחלה לתור, ואז שוב ושוב מוציאים קודקוד מהתור, מסמנים אותו כמבוקר ומכניסים לתור את כל שכניו שטרם בוקרו.
מכיוון שלרשימות השכנים אין סדר קבוע, שתי הרצות BFS תקינות עשויות להניב סדרי מעבר שונים. כדי שהתשובה תהיה חד-משמעית באתגר הזה, מיין את השכנים של כל קודקוד בסדר עולה לפני הכנסתם לתור.
אתגר
קלכתבו פונקציה bfs שמקבלת מערך דו־ממדי של int בשם adjacency (כל שורה היא קשת [u, v]) וערך int בשם start, ומחזירה את סדר הביקור בחיפוש לרוחב (BFS) החל מ־start כרשימה של ערכי int.
בנו את הגרף: עבור כל [u, v] בתוך adjacency, קראו ל־g.addEdge(u, v). לאחר מכן בצעו BFS החל מ־start באמצעות תור. בעת עיבוד השכנים של קודקוד, מיינו אותם בסדר עולה כדי שהפלט יהיה דטרמיניסטי.
עליכם להשתמש במחלקה Graph (המסופקת בתוך graph) — אל תשתמשו במבנים המובנים בשפה (כמו מפות וקבוצות) כדי לייצג את רשימות השכנות. נתוני עזר עבור האלגוריתם (קבוצות ביקור ותורים) יכולים להשתמש בטיפוסים של הספרייה הסטנדרטית.
נסו בעצמכם
#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;
}
כל השיעורים ביחידה גרפים – סדרת מבני נתונים מס' 9
תרגלו בעצמכם: קומפיילר C אונליין