Détecteur SCC de Tarjan

Pseudocode

Un seul DFS, une pile, deux nombres par sommet. L'idée clé est que toute composante fortement connexe possède une racine unique: le sommet de la composante découvert en premier.

connexionForte(u):
    dec[u] = low[u] = ++temps
    pile.empiler(u); surPile[u] = vrai

    pour chaque arete (u, v):
        si v non visite:
            connexionForte(v)
            low[u] = min(low[u], low[v])
        sinon si surPile[v]:
            low[u] = min(low[u], dec[v])
        // sinon: v est dans une CFC close, on ignore

    si low[u] == dec[u]:          // u est racine d une CFC
        depiler jusqu a u inclus
        cet ensemble depile est une CFC

Le test surPile est ce qui distingue Tarjan d'un schéma naïf de low-link. Une arête vers un sommet visité déjà affecté à une composante close n'apprend rien sur ta propre composante et doit être ignorée; l'inclure fusionnerait deux CFC réellement distinctes. Note aussi l'asymétrie: une arête d'arbre intègre low[v], une arête arrière intègre dec[v], et les confondre constitue l'autre bogue classique.

Exemple détaillé, étape par étape

Exécute Tarjan sur un graphe orienté contenant un cycle de trois sommets, un cycle de deux et un sommet n'appartenant à aucun des deux.

Graphe d'exemple: Arêtes orientées A vers B, B vers C, C vers A, B vers D, D vers E, E vers D, et C vers F.

1. Descendre A, B, C. dec et low démarrent égaux: A reçoit 1, B reçoit 2, C reçoit 3. Les trois sont sur la pile.
2. C vers A est une arête arrière. A est visité et toujours sur la pile, donc low[C] = min(3, dec[A] = 1) = 1. Note que cela utilise dec[A], pas low[A].
3. C vers F, et F se dépile seul. F reçoit dec 4 et n'a aucune arête sortante, donc low[F] reste à 4. Comme low[F] égale dec[F], F est racine d'une CFC et se dépile seul en tant que composante {F}. Un sommet sur aucun cycle forme toujours sa propre CFC singleton.
4. B vers D vers E, et E boucle en arrière. D reçoit dec 5, E reçoit dec 6. L'arête E vers D trouve D sur la pile, donc low[E] = min(6, dec[D] = 5) = 5. E n'est pas racine, puisque low[E] valant 5 diffère de dec[E] valant 6, rien ne se dépile encore.
5. D est une racine. De retour en D, low[D] = min(5, low[E] = 5) = 5, ce qui égale dec[D]. D est racine d'une CFC, la pile libère donc E puis D, donnant la composante {D, E}.
6. A est une racine. En remontant, low[B] = min(2, low[C] = 1, low[D] = 5) = 1 et low[A] = min(1, low[B] = 1) = 1, ce qui égale dec[A]. La pile libère C, B et A, donnant {A, B, C}.

Les low-link finaux sont A 1, B 1, C 1, F 4, D 5, E 5, et les composantes sortent dans l'ordre {F}, puis {D, E}, puis {A, B, C}. Deux points méritent attention. Les composantes sont émises dans l'ordre topologique inverse de la condensation, ce qui explique que Tarjan soit l'étape préalable habituelle pour 2-SAT. Et F, atteignable depuis le cycle mais sans retour possible, forme correctement sa propre composante au lieu d'être absorbé dans {A, B, C}.

Complexité et son origine

Temps: O(V + E) · Espace: O(V)

Un unique parcours en profondeur visite chaque sommet une fois et examine chaque arête orientée exactement une fois, d'où O(V + E). Chaque sommet est empilé une fois et dépilé une fois, les opérations de pile totalisent donc O(V) sur l'ensemble de l'exécution. L'état supplémentaire comprend la date de découverte, le low-link et l'indicateur sur-pile par sommet, plus la pile de récursion, le tout en O(V). Tarjan y parvient en une seule passe, là où Kosaraju exige deux parcours complets plus la construction du graphe transposé, raison pour laquelle Tarjan est généralement préféré en pratique bien que les deux soient linéaires.

Quand utiliser CFC de Tarjan, et quand l'éviter

Les trois algorithmes linéaires de CFC ont le même coût asymptotique, le choix porte donc sur les constantes, la mémoire et la facilité d'écrire un code correct.

Pièges fréquents

• Utiliser low[v] au lieu de dec[v] sur une arête arrière. Pour une arête d'arbre tu intègres low[v]; pour une arête arrière vers un sommet sur la pile tu intègres dec[v]. Utiliser low[v] sur les arêtes arrière peut importer une valeur venue d'une autre composante et fusionner des CFC qui devraient rester séparées. Les deux cas sont réellement distincts.
• Omettre le test surPile. Une arête vers un sommet visité déjà dépilé dans une CFC close doit être entièrement ignorée. Sans ce test, les low-link fuient entre composantes et la sortie est fausse sur tout graphe comportant des arêtes transverses.
• Oublier de réinitialiser surPile au dépilement. Tout sommet dépilé dans une composante doit voir son indicateur effacé. Le laisser actif fait que les tests d'arêtes arrière ultérieurs se déclenchent contre des sommets qui ne sont plus sur la pile, corrompant silencieusement les composantes suivantes.
• Récursivité sur de très grands graphes. Tarjan est naturellement récursif et la profondeur vaut la longueur du plus long chemin. Sur des graphes de centaines de milliers de sommets en chaîne, la pile d'appels déborde et une réécriture à pile explicite devient nécessaire. C'est plus délicat que pour un DFS simple, car la mise à jour du low-link doit intervenir après le retour de chaque fils.
• Supposer un ordre de composantes qui n existe pas. Tarjan émet les composantes dans l'ordre topologique inverse de la condensation, non dans un ordre lié aux étiquettes des sommets. Si tu as besoin de l'ordre topologique direct, inverse la sortie.

Questions fréquentes

Qu'est-ce qu'une composante fortement connexe?

Une composante fortement connexe d'un graphe orienté est un ensemble maximal de sommets dans lequel chaque sommet peut atteindre tous les autres en suivant des arêtes orientées. Le caractère maximal importe: on ne peut ajouter aucun autre sommet en conservant la propriété. Un sommet sur aucun cycle orienté forme à lui seul une composante.

Comment fonctionne l'algorithme de Tarjan?

Il exécute un unique parcours en profondeur en attribuant à chaque sommet un indice de découverte et une valeur low-link, le plus petit indice atteignable depuis son sous-arbre via au plus une arête arrière vers un sommet encore sur la pile. Les sommets sont empilés à leur visite. Lorsqu'un sommet se termine avec un low-link égal à son propre indice, il est racine d'une composante, et tout ce qui le surmonte sur la pile est dépilé comme cette composante.

Quelle est la différence entre les algorithmes de Tarjan et de Kosaraju?

Tous deux trouvent les composantes fortement connexes en O(V + E). Tarjan utilise un unique DFS avec comptabilité des low-link et une pile. Kosaraju utilise deux passes de DFS, une sur le graphe original pour les dates de fin et une sur le graphe transposé en ordre décroissant de fin. Kosaraju est plus simple à expliquer; Tarjan est plus rapide en pratique car il évite de construire la transposée et ne parcourt qu'une fois.

Quelle est la complexité temporelle de Tarjan CFC?

O(V + E) en temps et O(V) en espace. Chaque sommet est visité une fois, chaque arête examinée une fois, et chaque sommet empilé puis dépilé exactement une fois. C'est optimal, puisque tout algorithme doit lire le graphe entier.

À quoi servent les composantes fortement connexes?

À condenser un graphe orienté en un DAG, première étape de la résolution de 2-SAT. Également à l'analyse des graphes d'appels et à l'élimination de code mort dans les compilateurs, à la détection d'interblocages, à la recherche de dépendances mutuelles dans les gestionnaires de paquets et les tableurs, et à la structure communautaire des réseaux sociaux orientés.