Arborescence de Trémaux

  Un autre algorithme très ancien de parcours dans un graphe a été mis au point par un ingénieur du siècle dernier, Trémaux, dont les travaux sont cités dans un des premiers livres sur les graphes dû à Sainte Lagüe. Son but étant de résoudre le problème de la sortie d'un labyrinthe. Depuis l'avènement de l'informatique, nombreux sont ceux qui ont redécouvert l'algorithme de Trémaux. Certains en ont donné une version bien plus précise et ont montré qu'il pouvait servir à résoudre de façon très astucieuse beaucoup de problèmes algorithmiques sur les graphes. Il est maintenant connu sous l'appellation de Depth-first search nom que lui a donné un de ses brillants promoteurs: R. E. Tarjan. Ce dernier a découvert, entre autres, le très efficace algorithme de recherche des composantes fortement connexes que nous décrirons dans le paragraphe suivant.         L'algorithme consiste à démarrer d'un sommet et à avancer dans le graphe en ne repassant pas deux fois par le même sommet. Lorsque l'on est bloqué, on ``revient sur ses pas'' jusqu'à pouvoir repartir vers un sommet non visité. Cette opération de ``retour sur ses pas'' est très élégamment prise en charge par l'écriture d'une procédure récursive. Trémaux qui n'avait pas cette possibilité à l'époque utilisait un ``fil d'Ariane'' lui permettant de se souvenir par où il était arrivé à cet endroit dans le labyrinthe. On peut en programmation représenter ce fil d'Ariane par une pile.

  
Figure: Exécution de l'algorithme de Trémaux

Ceci donne deux versions de l'algorithme que nous donnons ci-dessous.  

procedure TremauxRec (u: Sommet; var pere: Arbo);
   var
       k: integer;
       v: Sommet;
   begin
   k := 1;
   v := succ[u, k];
   while (v <> Omega) do
       begin
       if (pere[v] = Omega) then
           begin
           pere[v] := u;
           TremauxRec(v, pere);
           end;
       k := k + 1;
       v := succ[u, k];
       end;
    end;

Le calcul effectif de l'arborescence de Trémaux de racine s'effectue en initialisant le vecteur pere et en effectuant l'appel de TremauxRec(x,pere):

for i := 1 to n do 
    pere[i] := Omega;
pere[x] := x;
TremauxRec(x,pere);

La figure explique l'exécution de l'algorithme sur un exemple, les appels de la procédure sont dans l'ordre:

TremauxRec(1)
     TremauxRec(2)
     TremauxRec(3)
         TremauxRec(6)
         TremauxRec(5)
     TremauxRec(4)

procedure TremauxPil (succ: GrapheSuc; n: integer; x: Sommet; 
                      var pere: Arbo);
    label 999;
    var
        p: Pile;
        i, u, v: Sommet;
        j: integer;
    begin
    for i := 1 to n do
        pere[i] := Omega;
    Pinitialiser(p);
    Pajouter(x, p);
    pere[x] := x;
    while not (Pvide(p)) do
        begin
        u := Pvaleur(p);
        j := 1;
        v := succ[u, j];
        if v <> Omega then
            while  pere[v] <> Omega do
                begin
                j := j + 1;
                v := succ[u, j];
                if v= Omega then goto 999;
                end;
        999:
        if (v <> Omega) then
            begin
            pere[v] := u;
            Pajouter(v, p);
            end
        else
            Psupprimer(p);
        end;
    end;

Remarques
  1 L'ensemble des sommets atteignables à partir du sommet est formé des sommets tels que Pere[y] Omega à la fin de l'algorithme, on a donc un algorithme qui répond à la question Existechemin(x,y) examinée plus haut avec un nombre d'opérations qui est de l'ordre du nombre d'arcs du graphe (lequel est inférieur à ), ce qui est bien meilleur que l'utilisation des matrices.

2 L'algorithme non récursif tel qu'il est écrit n'est pas efficace car il lui arrive de parcourir plusieurs fois les successeurs d'un même sommet; pour éviter cette recherche superflue, il faudrait empiler en même temps qu'un sommet le rang du successeur que l'on est en train de visiter et incrémenter ce rang au moment du dépilement. Dans ce cas, on a une bien meilleure efficacité, mais la programmation devient inélégante et le programme difficile à lire; nous préférons de loin la version récursive.

L'ensemble des arcs du graphe qui ne sont pas dans l'arborescence de Trémaux de racine est divisé en quatre sous-ensembles:

   
1. Les arcs dont l'origine n'est pas dans , ce sont les arcs issus d'un sommet qui n'est pas atteignable à partir de .

2. Les arcs de descente, il s'agit des arcs de la forme où est un descendant de dans , mais n'est pas un de ses successeurs dans cette arborescence.

3. Les arcs de retour, il s'agit des arcs de la forme où est un ancêtre de dans .

4. Les arcs transverses, il s'agit des arcs de la forme où n'est pas un ancêtre, ni un descendant de dans .

On remarquera que, si est un arc transverse, on aura rencontré avant dans l'algorithme de Trémaux.

  
Figure: Les arcs obtenus par Trémaux

Sur la figure , on a dessiné un graphe et les différentes sortes d'arcs y sont représentés par des lignes particulières. Les arcs de l'arborescence sont en traits gras, les arcs de descente en traits normaux (sur cet exemple, il y en a deux), les arcs dont l'origine n'est pas dans sont dessinés en pointillés, de même que les arcs de retour ou transverses qui sont munis d'une étiquette permettant de les reconnaître, celle ci est R pour les arcs de retour et Tr pour les arcs transverses. Les sommets ont été numérotés suivant l'ordre dans lequel on les rencontre par l'algorithme de Trémaux, ainsi les arcs de l'arborescence et les arcs de descente vont d'un sommet à un sommet d'étiquette plus élevée et c'est l'inverse pour les arcs de retour ou transverses.