L'algorithme peut être décrit comme suit :
Soit un graphe orienté à n sommets et m arêtes. Il est nécessaire de renuméroter ses sommets de manière à ce que chaque arête mène d'un sommet avec un numéro inférieur à un sommet avec un numéro supérieur.
En d'autres termes, il s'agit de trouver une permutation de sommets (ordre topologique) correspondant à l'ordre donné par toutes les arêtes du graphe.
Nous allons utiliser la recherche en profondeur (dfs(v))
Si nous ajoutons notre sommet au début d'une liste au moment de la sortie de \(dfs(v)\) , alors à la fin dans cette liste vous obtenez un tri topologique.
Ainsi, le tri topologique souhaité — ceci est trié par ordre décroissant des heures de sortie.