Chapitre 3 • Éléments de la théorie des graphes
98
**3.7 Déter mi na tion des compo santes for te ment connexes d’un
graphe : Algo rithme de Kosaraju et sharis
Don nées : un graphe g 5 (X, U)
où x 5 {x 1 , x 2 ,…, x n }
1. Effec tuer un par cours en pro fon deur sur le graphe g, à par tir du som met
x 1 : on obtient ainsi une arbo res cence de racine x 1 ; si des som mets n’ont
pas été visi tés (ils n’appar tiennent donc pas à cette arbo res cence), recom -
men cer à par tir du som met de plus faible indice non encore visité.
Et ainsi de suite jus qu’à ce que tous les som mets aient été visi tés. Le
« rang » π (x i ) du som met x i est par défi ni tion, le numéro d’ordre de fin
d’explo ra tion de x i (c- à-d de « postvisite », ou « fer me ture »).
2. Construire le graphe « miroir » g
t 5 (X, U
t
) obtenu à par tir de g en
inver sant tout arc de U ; g et g
t
ont le même ensemble de som mets ;
3. Effec tuer un par cours en pro fon deur sur g
t
, à par tir du som met de plus
fort rang ; noter l’arbo res cence asso ciée ; si tous les som mets n’ont pas
été visi tés, recom men cer à par tir du som met de plus fort rang non encore
visité. Et ainsi de suite jus qu’à ce que tous les som mets aient été visi tés.
On peut démon trer qu’à cha cune des arbo res cences obte nues dans le par ­
cours en pro fon deur de g
t
cor res pond une compo sante for te ment connexe
de g et une seule.
➤ APPLi cA TiON : Appli quer l’algo rithme de KOSARAJU et SHARIS au
graphe g ci- dessous :
(par commo dité, on a noté A pour x 1 , B pour x 2 , etc., H pour x 8 ).
H
C
D
G
F
E
B
A
N.B : dans le par cours en pro fon deur de g, si vous avez le choix entre plu sieurs
suc ces seurs ouvrables (non mar qués), ouvrir celui d’indice le plus petit