On considère dans cet exercice des graphes orientés acycliques, soit des graphes orientés sans circuit, représentés par listes de successeurs à l'aide de dictionnaires. Par exemple ;
Un ordre topologique sur un graphe est un ordre sur les sommets du graphe tel que, pour tout couple de sommets \(u\), \(v\) distincts, s'il existe un arc \(u \rightarrow v\), alors \(u\) précède \(v\) dans l'ordre. Dans ce cas, on note \(u \prec v\).
L'objectif de cet exercice est d'obtenir une liste des sommets ordonnés suivant un ordre topologique. Cette liste n'est pas nécessairement unique.
Par exemple, pour le graphe g, les deux listes ['D','E','A','B','C'] et ['E','A','D','B','C'] conviennent.
La figure ci-dessous reprend le graphe proposé plus haut et illustre deux ordres topologiques.
L'ordre topologique peut être utilisé afin de trier des tâches dépendants les unes des autres. Par exemple, lorsqu'une personne s'habille, il lui est possible de mettre un pantalon avant des chaussettes ou le contraire. Par contre elle ne peut pas mettre sa chemise avant son pull.
On modélise cette situation par un graphe dans lequel chaque sommet est une tâche et les arêtes illustrent les relations de dépendance.
On appelle degré entrant d'un sommet \(v\) le nombre d'arcs \(u \rightarrow v\), soit le nombre de prédécesseurs de \(v\).
On peut montrer que ;
tout graphe orienté acyclique possède au moins un sommet de degré entrant égal à \(0\), autrement dit il existe au moins un sommet sans prédécesseur ;
si un graphe orienté acyclique possède \(n\) sommets \(u_0, u_1, ..., u_{n-1}\), si le degré entrant de \(u_0\) est 0 et si \([u_1, ..., u_{n-1}]\) est triée, alors \([u_0, u_1, ..., u_{n-1}]\) est triée.
Cette dernière propriété est à la base de l'algorithme de Kahn dont le principe est le suivant ;
une liste vide est créée pour contenir les sommets triés ;
le degré entrant de chaque sommet est calculé et stocké à l'aide d'un dictionnaire ;
les sommets dont le degré entrant est égal à \(0\) sont placés dans une pile (ou une file, voir plus bas);
tant que la pile (file) n'est pas vide, un élément en est retiré, il est ajouté à la liste des sommets triés. Le degré entrant de tous ses successeurs est ensuite diminué d'une unité et les successeurs dont le nouveau degré entrant vaut \(0\) sont placés dans la pile (file);
la liste des sommets triés est renvoyée.
Afin de simplifier la mise en œuvre, on propose de stocker les sommets en attente de traitement dans une pile.
Compléter la fonction tri_topo qui prend en paramètre un dictionnaire graphe représentant un graphe orienté acyclique et renvoie une liste de sommets ordonnés selon un ordre topologique.
# Tests(insensible à la casse)(Ctrl+I)
(Alt+: ; Ctrl pour inverser les colonnes)
(Esc)