Tri topologique d'un graphe sans circuit

La relation d'accessibilité d'un graphe est un préordre qui n'est pas nécessairement un ordre (partiel): il se peut que $u\to^{\star}v$ et $v\to^{\star}u$ sans que u=v. Cette relation est un ordre si et seulement si le graphe est sans circuit. Les graphes sans circuit, qui constituent une généralisation des arborescences, interviennent dans de nombreuses applications, par exemple pour représenter une relation de précédence entre tâches, ou une relation de partage de sous-expressions. Une linéarisation de la relation d'ordre $\to^{\star}$ est une relation d'ordre total contenant cet ordre, c'est-à-dire une relation réflexive, anti-symétrique et transitive $\le$ telle que $u\to^{\star}v$ implique $u\le v$.

Un tri (ou un parcours) topologique   est une énumération des sommets d'un graphe sans circuit selon une linéarisation de sa relation d'accessibilité (figure 2.12) ; ce terme de topologique est traditionnel et mal choisi. Un parcours topologique peut être obtenu en modifiant le parcours en largeur (en calculant et utilisant le degré entrant de chaque sommet), ou en appliquant le parcours en profondeur. On peut montrer que l'énumération postfixe des sommets, au cours d'un parcours en profondeur, produit les sommets dans l'ordre inverse d'un ordre topologique. Par conséquent, il suffit d'utiliser une pile t et de choisir comme post-traitement l'empilement de l'objet à traiter sur cette pile ; une fois le parcours terminé, les dépilements successifs de t produiront une énumération des sommets dans l'ordre topologique.