Probleme – Kosaraju : pourquoi le second parcours ne déborde pas

1. Soit un arc $C\to C^{\prime }$ dans le quotient. Deux cas, selon celle des deux composantes que le parcours rencontre en premier.

Cas 1 : le parcours entre d'abord dans $C$, en un sommet $u$. Comme $C\to C^{\prime }$, tous les sommets de $C^{\prime }$ sont accessibles depuis $u$ ; comme aucun d'eux n'a encore été vu, la descente depuis $u$ les visitera tous et les terminera avant de terminer $u$ — c'est la propriété d'imbrication des appels récursifs. Donc $f(C)\ge \text{fin}(u)>f(C^{\prime })$.

Cas 2 : le parcours entre d'abord dans $C^{\prime }$, en un sommet $v$. Alors aucun sommet de $C$ n'est accessible depuis $v$ : sinon il y aurait un chemin de $C^{\prime }$ vers $C$, et avec l'arc $C\to C^{\prime }$ un cycle dans le quotient, qui est acyclique. La descente depuis $v$ termine donc tous les sommets de $C^{\prime }$ sans toucher à $C$, et $f(C^{\prime })<f(C)$ car $C$ sera visitée plus tard.

Dans les deux cas $f(C)>f(C^{\prime })$. Autrement dit, trier les composantes par $f$ décroissant est un tri topologique du quotient — c'est la propriété mesurée à l'exercice « Dérouler Kosaraju ».

2. Soit $u$ le sommet de plus grande date de fin, et $C$ sa composante ; alors $f(C)$ est maximal. S'il existait un arc $C^{\prime \prime }\to C$ dans le quotient, on aurait $f(C^{\prime \prime })>f(C)$ par la question 1, ce qui contredit la maximalité. Donc $C$ n'a aucun arc entrant : c'est une source du quotient.

3. La récurrence. Le second parcours démarre en $u$, dans $G^{\mathsf{T}}$. Par l'exercice « Le transposé garde les composantes », $C$ est une source de $G$, donc un puits de $G^{\mathsf{T}}$ : aucun arc de $G^{\mathsf{T}}$ ne sort de $C$. Le parcours depuis $u$ dans $G^{\mathsf{T}}$ atteint donc exactement $C$ — il atteint tout $C$ car $C$ est fortement connexe, et rien de plus car il ne peut pas en sortir.

On marque $C$ et on recommence. Le sommet non marqué de plus grande date de fin est, par le même argument appliqué au quotient privé des composantes déjà traitées, dans une source de ce quotient réduit. La récurrence porte sur le nombre de composantes restantes, et le cas de base est le quotient vide.

4. Complexité. Trois passes linéaires : le premier parcours en $\Theta (n+m)$, la transposition en $\Theta (n+m)$, le second parcours en $\Theta (n+m)$. Total $\Theta (n+m)$, avec un espace $\Theta (n+m)$ pour le graphe transposé.

Et l'on rend plus que les composantes. La numérotation produite est un tri topologique du quotient (question 1), vérifié sur $5000$ graphes aléatoires sans un seul arc à contresens. C'est ce supplément gratuit qui rend la décomposition utile : il permet de traiter les composantes dans un ordre où toute composante vient après celles dont elle dépend. C'est ce dont la programmation dynamique a besoin, et c'est ce dont le problème suivant se sert.

Une remarque sur la pile. Le code du chapitre est récursif ; sur un graphe de $10^6$ sommets formant un long chemin, la pile d'appels déborde. Une version itérative avec pile explicite est nécessaire en pratique — c'est le même arbitrage qu'à l'exercice « Compresser sans récursion » du chapitre chap:unir.