Algorithme de Tarjan

① Définitions fondamentales

Un graphe orienté est un ensemble de sommets reliés par des arcs (flèches). Une composante fortement connexe (CFC) est un sous-ensemble maximal de sommets tel que, pour toute paire (u, v), il existe un chemin de u vers v et de v vers u.

Variable	Signification	Moment d'affectation
d[u]	Date de découverte de u (premier passage)	À l'entrée dans u
t[u]	Valeur temporaire (plus petit d[] atteignable depuis u)	Initialisé à d[u], mis à jour en remontant
f[u]	Date de fin de traitement de u	À la sortie de u
Pile	Sommets découverts mais pas encore affectés à une CFC	Push à l'entrée, pop quand racine détectée

Règle racine : u est la racine d'une CFC si et seulement si t[u] = d[u] lors de la sortie de u. On dépile alors tous les sommets jusqu'à u inclus pour former la CFC.

② Algorithme (pseudo-code)

function Tarjan(G):
  date ← 0
  pile ← []
  pour tout sommet u faire  couleur[u] ← BLANC

  pour tout sommet u faire
    si couleur[u] = BLANC alors  Visiter(u)

function Visiter(u):
  couleur[u] ← GRIS
  date ← date + 1
  d[u] ← date          // date de découverte
  t[u] ← d[u]          // t initialisé à d
  push(pile, u)

  pour tout voisin v de u faire
    si couleur[v] = BLANC alors
      Visiter(v)
      t[u] ← min(t[u], t[v])   // remontée après retour
    sinon si v ∈ pile alors
      t[u] ← min(t[u], d[v])   // arc vers ancêtre en pile

  couleur[u] ← NOIR
  date ← date + 1
  f[u] ← date           // date de fin

  si t[u] = d[u] alors   // u est racine de CFC
    CFC ← []
    répéter
      w ← pop(pile)
      ajouter w à CFC
    jusqu'à w = u
    enregistrer(CFC)

1 Entrée : incrémenter le compteur global date, affecter d[u] = t[u] = date, empiler u, passer u en GRIS.

2 Exploration des voisins : si un voisin v est BLANC, appel récursif puis t[u] = min(t[u], t[v]). Si v est déjà en pile, t[u] = min(t[u], d[v]).

3 Sortie : incrémenter date, affecter f[u], passer u en NOIR.

4 Test racine : si t[u] = d[u], dépiler jusqu'à u inclus → nouvelle CFC détectée.

③ Mise à jour de t[u] — les deux cas

Cas 1 — Arc vers un sommet BLANC (non visité) :
On appelle Visiter(v) récursivement. Après le retour, on met à jour :
t[u] = min(t[u], t[v])
On utilise t[v] car t[v] contient déjà le meilleur ancêtre atteignable depuis v.

Cas 2 — Arc vers un sommet déjà EN PILE (GRIS) :
Le sommet v a déjà été découvert et est un ancêtre dans le DFS. On fait :
t[u] = min(t[u], d[v])
On utilise d[v] (et non t[v]) car v est un ancêtre direct atteignable.

Cas ignoré — Arc vers un sommet NOIR (hors pile) :
Si v est NOIR et n'est plus en pile, il appartient déjà à une CFC précédente. Cet arc ne peut pas créer de cycle avec u, on l'ignore.

④ Démonstration interactive — exemple fixe

Graphe exemple avec 5 sommets : A→B, B→C, C→A, B→D, D→E, E→D

PRÊT Cliquez sur Suivant pour démarrer.

Pile :

vide

Sommet	d[u]	t[u]	f[u]	CFC

⑤ Points clés à retenir

Complexité : O(|V| + |E|) — chaque sommet et chaque arc sont traités une seule fois.

Au moment de la découverte : t[u] = d[u] (toujours).
Au moment de la sortie : t[u] peut avoir diminué (si un cycle a été détecté).
Si t[u] = d[u] à la sortie, u est la racine de sa CFC.
Un sommet isolé (sans cycle) forme à lui seul une CFC de taille 1.
L'ordre de parcours DFS dépend de l'ordre des voisins dans la liste d'adjacence.
La pile garantit que tous les sommets de la même CFC sont contigus au sommet.