up:: [[graphe orienté]], [[algorithme de tri]]
#s/informatique #s/maths/graphes 

> [!definition] tri topologique d'un graphe orienté
> Soit $G$ un graphe orienté.
> Un tri topologique de $G$ est un [[relation d'ordre totale|ordre total]] des sommets pour lequel $a < b$ quand il existe un arc de $a$ vers $b$.
^definition


> [!info] Algorithme 1
> 1. trouver un noeud sans prédécesseur dans le graphe
> 2. retirer ce noeud du graphe (et l'ajouter dans l'ordre du tri)
> 3. recommencer


> [!info] Algorithme 2
> Contents