האתגר האחרון מס׳ 1
שיעור 8 מתוך 9 בקורס מיון טופולוגי – אלגוריתמים על גרפים של Coddy.
אתגר
בינוניהאלגוריתם של Kahn משמש גם לזיהוי מעגלים.
כתבו פונקציה בשם hasCycle שמקבלת את n ואת מערך edges השטוח (מכוון) ומחזירה 1 אם הגרף מכיל מעגל, או 0 אם הוא חסר מעגלים.
רמז: הריצו את האלגוריתם של Kahn. אם הוא מצליח למקם את כל n הקודקודים, הגרף חסר מעגלים; אם הוא נתקע כשנותרו קודקודים, יש מעגל.
נסו בעצמכם
#include <stdlib.h>
int hasCycle(int n, int* edges, int edges_size) {
// כתבו כאן את הקוד
return 0;
}
כל השיעורים ביחידה מיון טופולוגי – אלגוריתמים על גרפים
תרגלו בעצמכם: קומפיילר C אונליין