Pseudocodice

Lezione 4 di 9 del corso Ordinamento topologico - Algoritmi sui grafi di 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] conta gli archi entranti. Solo gli archi u -> v vengono aggiunti a indeg[v].
Scorrere i vertici 0..n-1 e prendere il primo con grado entrante 0 dà la scelta più piccola a ogni passaggio, quindi l'ordine è deterministico.
Impostare indeg[pick] = -1 è un modo semplice per contrassegnare un vertice come già inserito.

Provalo tu

Questa lezione non include una sfida di codice.