Algorithme de Tarjan — Wikipédia

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, mais a l'avantage de ne faire qu'une passe sur le graphe au lieu de deux.

L'algorithme prend en entrée un graphe orienté et renvoie une partition des sommets du graphe 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.

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.

 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.dansP := 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.dansP = oui          v.numAccessible := min(v.numAccessible, w.num)        si v.numAccessible = v.num        // v est une racine, on calcule la composante fortement connexe associée        C := ensemble vide        répéter          w := P.pop(), w.dansP := 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(v)     renvoyer partition  fin de fonction 

(en) Description de l'algorithme de Tarjan

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