מימוש (חלק 2)

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

כעת נעבור על כל הגרף בעזרת מחסנית.

אתגר

בינוני

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

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

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

כדי לבקר בשכנים בסדר עולה, דחפו אותם למחסנית מהגדול לקטן.

נסו בעצמכם

#include <stdlib.h>

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