Exercices de programmation pour classes préparatoires
Écrire une fonction tri_topologique(graphe) qui renvoie un tri topologique des sommets d'un graphe orienté acyclique (DAG). Le graphe est donné sous forme d'un dictionnaire d'adjacence {sommet: [successeurs]}. Lorsque plusieurs sommets peuvent être choisis à une même étape, on choisit celui qui est le plus petit dans l'ordre alphabétique/numérique (utiliser un tas min ou une liste triée).
| Appel | Résultat attendu |
|---|---|
| tri_topologique({'A': ['B', 'C'], 'B': ['D'], 'C': ['D'], 'D': []}) | ['A', 'B', 'C', 'D'] |
| tri_topologique({'A': [], 'B': []}) | ['A', 'B'] |
Connectez-vous pour soumettre du code.