Pseudokod

Lekcja 4 z 9 w kursie Sortowanie topologiczne – algorytmy grafowe w 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] zlicza krawędzie wchodzące. Tylko krawędzie u -> v zwiększają wartość indeg[v].
Przeszukiwanie wierzchołków 0..n-1 i wybieranie pierwszego o stopniu wejściowym 0 daje najmniejszy wybór w każdym kroku, dzięki czemu kolejność jest deterministyczna.
Ustawienie indeg[pick] = -1 to prosty sposób na oznaczenie wierzchołka jako już umieszczonego.

Spróbuj swoich sił

Ta lekcja nie zawiera wyzwania z kodem.