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, 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 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.
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.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
Notes et références
- R. E. Tarjan, « Depth-first search and linear graph algorithms », SIAM Journal on Computing, vol. 1, no 2, , p. 146–160 (lire en ligne [PDF]).
