TD d’algorithmique avanc´ee
Corrig´e du TD 9 : Tri topologique
Jean-Michel Dischler et Fr´ed´eric Vivien
Un tri topologique d’un graphe orient´e acyclique G = (S, A) est un ordre lin´eaire des sommets de G
tel que si G contient l’arc (u, v), u apparaˆıt avant v. Le tri topologique d’un graphe peut ˆetre vu comme un
alignement de ses sommets le long d’une ligne horizontale tel que tous les arcs soient orient´es de gauche `a
droite.
Attention : le tri topologique d’un graphe orient´e acyclique n’est pas forc´ement unique.
1. Proposez un tri topologique du graphe de la figure 1.
1
2
3
9
8
7
4
5
6
7
9
1
4
2
5
8
3
Advertisement
6
9
4
5
1
2
3
6
8
7
7
4
5
9
1
2
8
3
6
Fig. 1 – Exemple de graphe orient´e acyclique avec trois de ses tris topologiques possibles.
2. Modifiez l’algorithme de parcours en profondeur vu en cours pour qu’il calcule pour chaque nœud u sa
date de fin de traitement fin[u] (la date `a laquelle lui et ses fils ont ´et´e trait´es).
PP(G)
pour chaque sommet u de G faire couleur [u] ← Blanc
pour chaque sommet u de G faire si couleur [u] = Blanc alors Visiter-PP(G, u, couleur )
Visiter-PP(G, s, couleur )
Advertisement
couleur [s] ← Gris
pour chaque voisin v de s faire
si couleur [v] = Blanc alors Visiter-PP(G, v, couleur )
couleur [s] ← Noir
temps ← temps + 1
fin[s] ← temps
3. Quel lien pouvez-vous faire entre les dates de fin de traitement et un tri topologique ?
Si le graphe G contient l’arc (u, v), le traitement de u finira apr`es le traitement de v, et on aura donc
fin[u] > fin[v]. Trier les sommets par date de fin de traitements d´ecroissantes nous fournit donc un tri
topologique du graphe. La figure 2 pr´esente le graphe de la figure 1 o`u les nœuds ont ´et´e annot´es avec
des fins de date de traitement lors d’un parcours en profondeur (¡¡ racines ¿¿ successives : nœuds 1, 9,
4 et 7). On retrouve alors le troisi`eme des tris topologiques de la figure 1.
1
5
4
2
1
2
3
6
3
9
9
8
7
8
Advertisement
7
1
4
5
6
Fig. 2 – Graphe annot´e par les dates de fin de traitement d’un parcours en profondeur.
4. Proposez un algorithme de tri topologique. Quel est sa complexit´e ?
On commence par parcourir le graphe en profondeur avec l’algorithme de la question 2, puis on trie les
sommets par date de fin d´ecroissante. La complexit´e de l’ensemble est donc celle du parcours O(|S|+|A|)
plus celle du tri O(|S| log(|S|)), soit O(|S| log(|S|) + |A|).
5. Am´eliorez votre algorithme pour qu’il soit de complexit´e lin´eaire.
PP(G)
Soit P une pile initialement vide
pour chaque sommet u de G faire couleur [u] ← Blanc
pour chaque sommet u de G faire si couleur [u] = Blanc alors Visiter-PP(G, u, couleur , P )
tant que non Pile-Vide(P ) faire
u ← D´epiler(P )
Afficher(u)
Visiter-PP(G, s, couleur , P )
couleur [s] ← Gris
pour chaque voisin v de s faire
si couleur [v] = Blanc alors Visiter-PP(G, v, couleur , P )
couleur [s] ← Noir
Empiler(P ,s)
On stocke dans une pile les ´el´ements dans l’ordre dans lequel leur traitement se termine. On retirera
les ´el´ements de la pile dans l’ordre inverse de celui dans lequel ils ont ´et´e ins´er´es (une pile fonctionne
Advertisement
toujours sur le mode ¡¡ premier entr´e, dernier sorti ¿¿). Utiliser une pile plutˆot que simplement les
dates de fin de traitement nous ´evite d’avoir `a trier ces dates (ce qui nous coˆuterait O(|S| log(|S|)).
L’algorithme complet a ici un coˆut de O(|S|+|A|) (le parcours est de coˆut O(|S|+|A|) et la pile contient
|S| ´el´ements, donc les d´epiler est de coˆut O(|S|)).
6. Proposez un autre algorithme de tri topologique, bas´e cette fois-ci sur le fait qu’un sommet de degr´e
entrant nul peut ˆetre plac´e en tˆete d’un tri topologique. Quelle est la complexit´e de cet algorithme ?
La figure 3 pr´esente le second algorithme de tri topologique. Un sommet qui est plac´e dans la file, est
un sommet dont tous les pr´ed´ecesseurs ont d´eja ´et´e ordonn´es : on peut donc le placer a son tour dans
l’ordre sans risquer de violer un arc. La complexit´e de l’ensemble est une fois de plus en O(|S| + |A|).
2
Tri-Topologique(G = (S, A))
Soit F une file initialement vide
pour chaque sommet u de G faire
degr´e(u) ← degr´e entrant de u
si degr´e(u) = 0 alors Insertion(F , u)
tant que non File-Vide(F ) faire
u ← Suppression(F )
Afficher(u)
pour chaque voisin v de u faire
degr´e(v) ←degr´e(v) − 1
si degr´e(v) = 0 alors Insertion(F , v)
Fig. 3 – Deuxi`eme algorithme de tri topologique.
3