Algorithmes de Parcours et Composantes Fortement Connexes

1. Définition des Composantes Fortement Connexes (CFC)

Dans un graphe orienté $G=(V,A)$, deux sommets $u$ et $v$ sont dits mutuellement accessibles s'il existe un chemin de $u$ vers $v$ ET un chemin de $v$ vers $u$.

Cette relation de mutuelle accessibilité est une relation d'équivalence. Ses classes d'équivalence sont appelées les composantes fortement connexes du graphe.

Une composante fortement connexe est donc un sous-ensemble maximal de sommets tel que pour toute paire de sommets $(u,v)$ dans cet ensemble, on peut aller de $u$ à $v$ et de $v$ à $u$.

La vidéo suivante introduit ce concept de manière très claire, en le contrastant avec la connexité simple des graphes non orientés.

2. Algorithme de Kosaraju : Une approche en deux passes

Comment identifier ces CFC de manière algorithmique ? Un simple parcours en profondeur (DFS) depuis un sommet arbitraire ne suffit pas. Comme le montre le début de la vidéo suivante, un tel parcours peut "déborder" d'une CFC pour en visiter d'autres.

L'algorithme de Kosaraju propose une solution élégante en deux passes, toutes deux basées sur le DFS.

1. Première passe : On effectue un DFS sur le graphe original $G$. L'objectif est de déterminer les dates de fin de traitement de chaque sommet. Une manière simple de s'en souvenir est d'empiler les sommets sur une pile au fur et à mesure qu'ils deviennent noirs (c'est-à-dire, après avoir exploré tous leurs descendants). Le sommet au sommet de la pile est celui qui a terminé en dernier.

2. Deuxième passe :
   a. On calcule le graphe transposé, noté $G^T$, obtenu en inversant le sens de tous les arcs de $G$.
   b. On effectue un DFS sur $G^T$. La boucle principale de ce DFS ne choisit pas les sommets dans un ordre arbitraire, mais dans l'ordre de fin de traitement décroissant de la première passe (c'est-à-dire en les dépilant de la pile créée à l'étape 1).
   c. Chaque arbre de la forêt DFS obtenue lors de cette seconde passe correspond exactement à une composante fortement connexe.

La vidéo ci-dessous détaille admirablement cet algorithme.

Synthèse de l'algorithme de Kosaraju

Soit un graphe orienté $G=(V,A)$.

1. Appeler DFS(G) pour calculer les dates de fin $f[u]$ pour tout sommet $u$. (Ou empiler les sommets à la fin de leur visite).
2. Calculer $G^T$.
3. Appeler DFS(G^T), mais dans la boucle principale, considérer les sommets par ordre décroissant de $f[u]$.
4. Les arbres de la forêt de parcours de la 2ème étape sont les CFC de $G$.

La complexité de l'algorithme est dominée par les deux parcours DFS. Le calcul du graphe transposé est aussi en $\mathcal{O}(|V|+|A|)$. La complexité totale est donc $\mathcal{O}(|V|+|A|)$, ce qui est optimal.

3. Algorithme de Tarjan : Une approche en une seule passe

Il existe un autre algorithme classique, souvent jugé plus subtil, qui identifie les CFC en une seule passe de DFS : l'algorithme de Tarjan. Il est essentiel de le connaître pour l'Agrégation.

L'idée est d'associer à chaque sommet $u$ deux valeurs lors du DFS :

• d[u], la date de découverte (un simple compteur incrémenté à chaque visite).
• low[u] (ou r[u] dans certaines notations), la plus petite date de découverte accessible depuis $u$ (y compris $u$ lui-même) en suivant des arcs de l'arbre DFS, puis au plus un arc "retour" (un arc menant d'un sommet à un de ses ancêtres dans l'arbre DFS).

Un sommet $u$ est la racine d'une CFC si et seulement si d[u] == low[u].

Lors du DFS, on maintient une pile des sommets en cours de visite. Quand on identifie une racine $u$, tous les sommets sur la pile jusqu'à $u$ (inclus) forment une CFC.

Le document ci-dessous fournit une explication formelle, le pseudo-code et une preuve de correction de l'algorithme de Tarjan.

La complexité de l'algorithme de Tarjan est également de $\mathcal{O}(|V|+|A|)$. Bien que plus complexe à appréhender, son implémentation en une seule passe le rend souvent plus efficace en pratique.

Conclusion

La notion de composante fortement connexe est un des piliers de l'analyse structurelle des graphes orientés. Sa maîtrise est non négociable pour votre concours.

Points clés à retenir :

• Une CFC est un ensemble maximal de sommets mutuellement accessibles dans un graphe orienté.
• L'algorithme de Kosaraju identifie les CFC en deux passes de DFS : la première sur $G$ pour ordonner les sommets, la seconde sur $G^T$ pour extraire les composantes. Son principe est robuste et plus simple à démontrer.
• L'algorithme de Tarjan est une méthode plus avancée en une seule passe, qui utilise des valeurs de "low-link" pour identifier les racines des CFC durant le parcours.
• Les deux algorithmes ont une complexité linéaire en $\mathcal{O}(|V|+|A|)$, ce qui est optimal. Ils illustrent la puissance du parcours en profondeur comme outil d'investigation algorithmique.

Prochaine étape :
Nous avons jusqu'ici exploré la structure de "qui peut atteindre qui". Dans notre prochaine leçon, nous introduirons une nouvelle dimension : le coût des déplacements. Nous commencerons à étudier les algorithmes de plus court chemin dans les graphes pondérés, en débutant par le célèbre algorithme de Dijkstra.