Algorithme de Tarjan

En théorie des graphes, l'algorithme de Tarjan permet de déterminer les composantes fortement connexes d'un graphe orienté^[1]. Il porte le nom de son inventeur, Robert Tarjan. L'algorithme de Tarjan est de complexité linéaire, comme l'algorithme de Kosaraju (en), mais a l'avantage de ne faire qu'une passe sur le graphe au lieu de deux.

Description

L'algorithme prend en entrée un graphe orienté et renvoie une partition des sommets du graphes correspondant à ses composantes fortement connexes.

Le principe de l'algorithme est le suivant : on lance un parcours en profondeur depuis un sommet arbitraire. Les sommets explorés sont placés sur une pile P. Un marquage spécifique permet de distinguer certains sommets : les racines des composantes fortement connexes, c'est-à-dire les premiers sommets explorés de chaque composante (ces racines dépendent de l'ordre dans lequel on fait le parcours, elles ne sont pas fixées de façon absolue sur le graphe). Lorsqu'on termine l'exploration d'un sommet racine v, on retire de la pile tous les sommets jusqu'à v inclus. L'ensemble des sommets retirés forme une composante fortement connexe du graphe. S'il reste des sommets non atteints à la fin du parcours, on recommence à partir de l'un d'entre eux.

Repérage des racines

Les sommets sont numérotés dans l'ordre où ils sont explorés. Le numéro d'un sommet est noté v.num.

Les arêtes empruntées par le parcours en profondeur forment un arbre. Dans ce contexte, on peut définir le sous-arbre associé à tout sommet v. Au cours de l'exploration de ce sous-arbre, on calcule une seconde valeur v.numAccessible. Elle est initialisée à v.num et décroît lors du parcours des successeurs de v. Lorsque le parcours de v se termine, v.numAccessible correspond au numéro du plus petit sommet situé soit dans le sous-arbre de v, soit successeur direct appartenant à P d'un sommet de ce sous-arbre.

Deux cas sont possibles :

• v est une racine. Alors tous les sommets accessibles depuis v sont dans le sous-arbre de v (à l'exception éventuelle de ceux explorés lors d'un parcours antérieur). On a v.numAccessible = v.num.
• v n'est pas une racine. Alors il existe un sommet accessible depuis v qui est dans P mais pas dans le sous-arbre de v. On a alors v.numAccessible < v.num.

Pseudo-code

 fonction tarjan(graphe G)
   num := 0
   P := pile vide
   partition := ensemble vide
 
   fonction parcours(sommet v)
     v.num := num
     v.numAccessible := num
     num := num + 1
     P.push(v), v.dans_P := oui
 
     // Parcours récursif
     pour chaque w successeur de v
       si w.num n'est pas défini
         parcours(w)
         v.numAccessible := min(v.numAccessible, w.numAccessible)
       sinon si w.dans_P = oui
         v.numAccessible := min(v.numAccessible, w.num)
 
     si v.numAccessible = v.num
       // C'est une racine, calcule la composante fortement connexe associée
       C := ensemble vide
       répéter
         w := P.pop(), w.dans_P := non
         ajouter w à C
       tant que w différent de v
       ajouter C à partition
   fin de fonction
 
   pour chaque sommet v de G
     si v.num n'est pas défini
       parcours(G, v)
 
   renvoyer partition
 fin de fonction

Notes et références

Liens externes

• (en) Description de l'algorithme de Tarjan

• Portail des mathématiques
• Portail de l'informatique théorique