Algorithme de Tarjan
En théorie des graphes, l'algorithme de Tarjan permet de déterminer les composantes fortement connexes d'un graphe orienté. 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

Lien externe
 Description de l'algorithme de Tarjan

Tarjan