מימוש (חלק 2)

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

כעת נסיר שוב ושוב קודקודים שדרגת הכניסה שלהם היא 0 כדי לבנות את הסדר.

אתגר

בינוני

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

כתבו פונקציה בשם topologicalSort שמקבלת את n ואת מערך edges השטוח (מכוון u -> v), ומחזירה סדר טופולוגי של הקודקודים.

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

בחירת הקודקוד הזמין הקטן ביותר בכל צעד הופכת את התשובה לייחודית.

נסו בעצמכם

#include <stdlib.h>

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