Motivazione

Un ordinamento topologico esiste solo quando il grafo non contiene cicli. Ne costruiamo uno con l'algoritmo di Kahn, che rimuove ripetutamente un vertice senza archi entranti rimanenti.

Perché imparare l'ordinamento topologico?

• Ordinamento con vincoli: sistemi di compilazione, pianificazione delle attività, prerequisiti dei corsi e ricalcolo dei fogli di calcolo si basano tutti su di esso.
• Rilevamento dei cicli: se non riesci a ordinare tutti i vertici, il grafo deve contenere un ciclo.
• Fondamento per gli algoritmi sui DAG: i cammini più brevi e più lunghi in un DAG si calcolano in ordine topologico.

Possono esistere molti ordinamenti validi. Per ottenere una risposta prevedibile, rimuoviamo sempre il vertice con il numero più piccolo il cui grado entrante è 0.