11.5. Tri topologique inverse

Dans un graphe orienté où les arcs reflètent une relation de précédence entre les sommets, le sens des arcs dépend directement de l'interprétation qu'on leur donne. Ainsi, un arc allant de x vers y peut être interprété comme signifiant que x doit être traité avant y ou bien, au contraire, que le sommet x "dépend" du sommet y et doit, par conséquent être traité après y.

Exemple : pour un programme, on aurait un arc partant d'un symbole vers les autres symboles utilisés dans sa définition. Ceci permet d'indiquer l'ordre dans lequel les symboles doivent être introduits afin qu'aucun ne soit utilisé avant d'avoir été défini.

Dans ce cas il faut représenter les sommets dans l'ordre inverse; c'est le tri topologique inverse. Pour notre exemple on a alors :

D E F C B I H G A K M L J

Ici les arcs iraient de droite à gauche.

Cependant la distinction entre tri topologique direct et inverse n'est pas fondamentale car :

Faire le tri topologique inverse d'un graphe orienté acyclique est équivalent à faire le tri topologique direct du graphe obtenu en inversant le sens des arcs. Pour une matrice de connectivité, inverser les arcs revient à faire une transposition de matrice.

Si on considère l'algorithme de recherche "en profondeur", on peut le modifier pour lui faire faire le tri topologique inverse simplement en insérant l'instruction :

    write(nom(IndexSommet))

juste avant de terminer la procédure Visite. Cette modification a pour effet d'imprimer la liste correspondant au tri topologique inverse lorsque le graphe traité par DFS est un graphe orienté acyclique. En effet, on imprime le nom d'un sommet après (ou à la fin de la procédure) avoir imprimé les noms des sommets vers lesquels il pointe.

Le mécanisme de la récursivité insère dans la pile les sommets à l'entrée de la procédure Visite et les ressort pour les imprimer à la sortie : l'ordre est donc l'inverse de l'ordre d'entrée et comme, partant d'un sommet, on suit sa "filiation" jusqu'à rencontrer un sommet déjà visité ou jusqu'à rencontrer un "cul-de-sac", on obtient bien une liste représentant l'ordre topologique inverse.

Si l'on n'est pas sûr que le graphe est bien acyclique, on peut modifier l'algorithme de parcours de façon à détecter les cycles de la manière suivante :

procedure TriTopoInverse(NbSommets: integer );
{
  Algorithme de tri topologique inverse basé sur
  le DFS avec représentation par matrice de connectivité.
  Les déclarations globales ainsi que la lecture
  du graphe sont décrites au paragraphe 11.2.2.
  Cette version détecte la présence de cycles éventuels.
}
var i,
    CmptrVisite,
    IndexSommet : 0..MaxNbSommets;

    NumDOrdre : array[1..MaxNbSommets] of integer;
    Parcouru:array[1..MaxNbSommets] of boolean;

procedure Visite (IndexSommet : integer);
var AutreSommet : integer;
begin
  CmptrVisite := CmptrVisite + 1;
  NumDOrdre[IndexSommet] := CmptrVisite;
  Parcouru[IndexSommet] := true;
  for AutreSommet := 1 to NbSommets do
    if Relie[IndexSommet, AutreSommet] then
      if Parcouru[AutreSommet] then
        writeln(Nom[AutreSommet], ' fait partie d''un cycle')
      else if NumDOrdre[AutreSommet] = 0
           then Visite (AutreSommet);
  Parcouru[IndexSommet] := false;
  write(Nom[IndexSommet]);
end; { Visite }

begin { TriTopoInverse }
  CmptrVisite := 0;
  for IndexSommet := 1 to NbSommets do
    NumDOrdre[IndexSommet]:=0;
  for IndexSommet := 1 to NbSommets do
    if NumDOrdre[IndexSommet]=0 then begin
      for i := 1 to NbSommets do Parcouru[i] := false;
      Visite (IndexSommet);
      end; { if }
end; { TriTopoInverse }

Si un graphe orienté contient un cycle, c'est-à-dire que, partant d'un sommet, on y revient après avoir parcouru plusieurs arcs dans le sens indiqué, ce n'est pas un graphe acyclique et il ne peut donc pas faire l'objet d'un tri topologique.

Exercices

11.6. Composante fortement connexe d'un graphe orienté

Table des matières.

Site Hosting: Bronco