Overview
Le tri topologique ordonne linéairement les nœuds d'un DAG de sorte que chaque arête va d'un nœud antérieur à un nœud postérieur.
Analogy
Comme planifier des tâches avec des dépendances — tu dois terminer les prérequis avant d'avancer.
Step-by-step
- Calcule le degré entrant de chaque nœud
- Ajoute tous les nœuds avec degré entrant 0 à une file
- Retire un nœud, ajoute à l'ordre, réduit le degré des voisins
- Si un voisin atteint le degré 0, ajoute-le à la file
Visual
A→C, B→C, C→D
Degrés: A=0,B=0,C=2,D=1
File:[A,B]→traite A→C=1
File:[B]→traite B→C=0→[C]→D
Common mistakes
- Appliquer à des graphes avec des cycles (pas un DAG)
- Oublier de gérer les nœuds déconnectés
Practice questions
- Tri topologique du planning de cours
- Détecte les cycles en vérifiant si tous les nœuds ont été traités