פסאודו-קוד

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

topologicalSort(n, edges):
   build directed adjacency; compute indeg[v] for all v
   order = []
   repeat n times:
      pick = smallest v with indeg[v] == 0 (none left -> stop)
      mark pick as used (indeg[pick] = -1)
      order.add(pick)
      for nb in adj[pick]:
         indeg[nb] -= 1
   return order

indeg[v] סופר את הקשתות הנכנסות. רק קשתות u -> v מתווספות ל-indeg[v].
סריקת הקודקודים 0..n-1 ובחירת הראשון שדרגת הכניסה שלו היא 0 נותנות את הבחירה הקטנה ביותר בכל צעד, ולכן הסדר הוא דטרמיניסטי.
הצבת indeg[pick] = -1 היא דרך פשוטה לסמן שקודקוד כבר הוצב.

נסו בעצמכם

השיעור הזה לא כולל אתגר קוד.