TD d'informatique No. 10 : Tri topologique

Patrick Gros -- Patrick.Gros@irisa.fr
Didier Le Botlan -- didier.le_botlan@inria.fr

Lundi 29 janvier 2001

On considère un graphe orienté représentant un ensemble de tâches à effectuer. Une arête allant d'un sommet a vers un sommet b indique que la tâche a doit être effectuée avant que b puisse l'être. Sachant qu'on ne peut exécuter qu'une seule tâche à la fois, faire un tri topologique du graphe consiste à construire une liste proposant un ordre d'exécution des tâches : on doit pouvoir exécuter la première tâche indiquée par la liste, puis la deuxième... en respectant les contraintes données par le graphe.

Pour construire une telle liste, on utilise un tableau auxiliaire donnant pour chaque sommet le nombre d'arêtes qui y arrivent. On procède alors dans l'ordre suivant :
  1. on initialise la tableau à partir de la matrice d'adjacence du graphe ;
  2. on cherche un sommet s qui n'a pas de prédécesseur et on le met dans la liste ; la case correspondante du tableau est mise à -1 ;
  3. on signale à tous les sommets liés à s que s est dans la liste ;
  4. on itère tant qu'il reste des sommets ;
  5. si on a construit la liste à l'envers, on la retourne ;
  6. on affiche la liste ainsi construite.
Il est demandé de construire une vraie liste (avec des pointeurs), et de ne pas utiliser de tableau pour produire le résultat du tri.

Pour partir plus vite, on pourra récupérer les fichiers Sommet.java, Graphe.java, graphe1 et graphe2 dans ~pgros/tc_00_01

This document was translated from LATEX by HEVEA.