Tri Topologique
DAG — ordre d'exécution des tâches
Enonce
Implémenter le tri topologique par DFS sur un DAG. Tester sur un graphe de dépendances de cours.
G = {5:[2,0], 4:[0,1], 2:[3], 3:[1], 1:[], 0:[]}
Signature attendue
def tri_topologique(G: dict) -> list:Exemple
tri_topologique({5:[2,0], 4:[0,1], 2:[3], 3:[1], 1:[], 0:[]})→[4, 5, 0, 2, 3, 1]
📖 Rappel de cours
Le tri topologique ordonne les sommets d'un DAG (graphe orienté acyclique) tel que pour chaque arc $(u,v)$, $u$ apparaît avant $v$.
Algorithme (DFS post-ordre inversé) :
1. DFS complet. Quand un sommet est terminé (tous ses voisins visités), l'ajouter en tête.
2. Le résultat est un tri topologique.
Alternative (algorithme de Kahn) :
File des sommets de degré entrant 0. Retirer, décrémenter les voisins, ajouter les nouveaux de degré 0.
Un tri topologique n'existe que si le graphe est acyclique.
← Exercices sur les graphes en Python — BFS, DFS, Dijkstra
Exercices du meme theme
- Algorithme de Dijkstra
- Composantes Connexes
- Détection de Cycle dans un Graphe Non Orienté
- Algorithme de Bellman-Ford
- Algorithme de Prim
- Algorithme de Kruskal
La correction commentee, les indices progressifs, l'execution du code dans le navigateur et la verification par l'IA sont reserves aux abonnes.