מימוש (חלק 2)

שיעור 6 מתוך 9 בקורס חיפוש לרוחב – אלגוריתמים על גרפים של Coddy.

כעת נעבור על הגרף בשכבות באמצעות תור.

אתגר

בינוני

עכשיו בנו את הסריקה המלאה.

כתבו פונקציה בשם bfs שמקבלת את n, את המערך השטוח edges (לא מכוון) ואת קודקוד ההתחלה start, ומחזירה את סדר הביקור של BFS בקודקודים, החל מ-start.

בנו את רשימת השכנויות (השכנים ממוינים בסדר עולה), ואז השתמשו בתור: סמנו והוסיפו לתור את קודקוד ההתחלה, ולאחר מכן הוציאו ממנו שוב ושוב קודקוד, תעדו אותו והוסיפו לתור את שכניו שטרם בוקרו. מבקרים רק בקודקודים שניתן להגיע אליהם מ-start.

נסו בעצמכם

#include <stdlib.h>

int* bfs(int n, int* edges, int edges_size, int start, int* returnSize) {
    // כתבו כאן קוד
    *returnSize = 0;
    return edges;
}