Composantes fortement connexes avec Kosaraju

Une composante fortement connexe (SCC) d’un graphe orienté est un ensemble maximal de sommets tel qu’il existe un chemin de chaque sommet vers tout autre sommet de l’ensemble. Par exemple, si les sommets A, B et C forment un cycle (A→B→C→A), ils appartiennent tous à la même SCC. Un sommet isolé, sans boucle sur lui-même, constitue sa propre SCC. Les SCC révèlent la structure cyclique d’un graphe orienté.

L’algorithme de Kosaraju trouve toutes les SCC en O(V + E) à l’aide de deux passes DFS. Passe 1 : exécutez DFS sur le graphe d’origine et empilez les sommets selon leur ordre de terminaison, c’est-à-dire en postordre. Passe 2 : exécutez DFS sur le graphe transposé, ou inversé, en traitant les sommets dans l’ordre inverse de leur terminaison, en utilisant pop sur la pile. Chaque arbre DFS de la passe 2 constitue une SCC.

Lors de la passe 1, la SCC dont l’arbre DFS se termine en dernier est celle qui n’a pas d’arcs sortants vers d’autres SCC, une SCC « puits » dans le DAG de condensation. Dans le graphe transposé, cette SCC n’a aucun arc entrant provenant d’autres SCC : un DFS lancé depuis celle-ci reste donc confiné à cette SCC pendant la passe 2. Chaque DFS suivant de la passe 2 reste dans sa propre SCC, car tous les arcs entre SCC ont été inversés et ramènent vers des SCC déjà visitées.

Exécutez DFS sur le graphe d’origine et empilez chaque sommet lorsqu’il a terminé, en postordre. Les composantes ne nous intéressent pas pendant cette passe : seul l’ordre de terminaison compte. Le dernier sommet à terminer appartiendra à une SCC « source » du DAG de condensation.

Utilisez pop pour retirer les sommets de la pile des terminaisons, en commençant par le plus grand temps de terminaison, puis exécutez DFS sur le graphe transposé. Chaque DFS lancé depuis un sommet non visité découvre exactement une SCC. Marquez tous les sommets atteints par ce DFS comme appartenant à la même composante.

Le graphe transposé inverse chaque arc : si le graphe d’origine contient u → v, le graphe transposé contient v → u. La transposition conserve les SCC : si A et B appartiennent à la même SCC dans le graphe d’origine, ils restent dans la même SCC dans le graphe transposé, puisque tous les chemins sont inversés mais restent connectés. Construire le graphe transposé lors de la lecture des entrées, comme ci-dessus, évite une étape de transposition distincte.

Pour les grands graphes, remplacez le DFS récursif par un DFS itératif utilisant une pile explicite afin d’éviter la limite de récursion de Python. La version itérative empile les nœuds, les traite et conserve un marqueur « retour » distinct pour simuler un parcours en postordre.

L’algorithme de Tarjan trouve les SCC en un seul parcours DFS, contre deux parcours pour celui de Kosaraju. Il maintient une pile de nœuds et attribue à chaque nœud un temps de découverte et une valeur de lien faible. Lorsque le temps de découverte d’un nœud est égal à sa valeur de lien faible, ce nœud est la racine d’une SCC. L’algorithme de Tarjan est légèrement plus complexe à implémenter, mais évite de construire le graphe transposé. Les deux algorithmes sont en O(V + E).

Les SCC sont utilisées pour : (1) l’optimisation des compilateurs — identifier les fonctions mutuellement récursives ; (2) l’analyse des réseaux sociaux — trouver les communautés très soudées ; (3) le problème 2-SAT — déterminer la satisfiabilité de clauses à deux littéraux ; (4) l’exploration du Web — identifier les groupes de pages comportant de nombreux liens croisés ; (5) la condensation DAG — après avoir trouvé les SCC, la condensation du graphe est un DAG, ce qui permet l’analyse topologique de graphes cycliques.

La condensation d’un graphe orienté contracte chaque SCC en un nœud unique et ajoute une arête entre deux super-nœuds s’il existe une arête entre leurs SCC constitutives. Le résultat est toujours un DAG — vous pouvez y exécuter un tri topologique. Cela permet d’appliquer à des graphes orientés généraux des algorithmes qui ne fonctionnent que sur les DAG, comme DP, en travaillant sur leur condensation.

Le nombre de SCC dans un graphe orienté révèle sa structure cyclique. Un DAG possède n SCC, car chaque nœud constitue sa propre SCC. Un graphe fortement connexe possède exactement 1 SCC. En général, les SCC forment un DAG une fois condensées : c’est la condensation. Si le DAG de condensation possède une source unique, c’est-à-dire un nœud de degré entrant 0, et un puits unique, c’est-à-dire un nœud de degré sortant 0, certaines propriétés de connexité sont vérifiées dans la condensation. Ces propriétés sont étudiées dans des problèmes portant sur l’accessibilité après l’ajout d’un nombre minimal d’arêtes.

Dans cette leçon, vous avez appris que : les SCC sont des ensembles maximaux dans lesquels chaque nœud est accessible depuis tous les autres ; Kosaraju utilise deux parcours DFS — le premier sur le graphe initial pour déterminer l’ordre de fin, puis le second sur le graphe transposé ; et la condensation de tout graphe orienté est un DAG utilisable pour poursuivre l’analyse. Nous allons ensuite construire des structures de données TrieNode pour insert, search et les opérations sur les préfixes.