Pour les graphes non-orientés nous avions défini une composante connexe comme étant un ensemble de sommets tel qu'il existait toujours un chemin entre deux sommets de cet ensemble. Deux sommets reliés par un arc faisait forcément partie de la même composante connexe.
D'une manière similaire, pour un graphe orienté, on peut définir une composante fortement connexe comme étant un ensemble de sommets tel qu'il existe toujours un chemin entre deux sommets de cet ensemble. Cette définition implique que tous les sommets d'une composante connexe font partie d'un même cycle. Deux sommets reliés par un arc ne font donc pas forcément partie de la même composante.
En fait, les sommets se subdivisent en composantes fortement connexes, qui ont la propriété que tous les sommets d'une composante soient accessibles depuis les autres et réciproquement. Mais il est impossible d'aller d'un sommet d'une composante à un sommet d'une autre composante et retour. Deux composantes fortement connexes d'un graphe sont soit entièrement disjointes, soit reliées par un ou plusieurs arcs qui vont tous dans le même sens (les arcs partent tous de la même composante pour arriver dans l'autre)
Les composantes fortement connexes du graphe-exemple du début de ce chapitre (figure 11.1.) sont :
Dans cet exemple, le sommet A est dans une autre composante connexe que F car il y a bien un chemin menant de A à F mais il n'y a aucun moyen d'aller de F à A.
A l'aide de la matrice de fermeture transitive (appelons la M), il est possible de déterminer si deux sommets x et y font partie de la même composante fortement connexe : il suffit que M[x,y]=M[y,x]=1.
Comme on peut s'y attendre, la méthode pour déterminer les composantes fortement connexes d'un graphe orienté repose sur l'algorithme de DFS. La variante de l'algorithme de DFS proposée plus loin est due à R.E. Tarjan (1972) dont l'article entier mérite d'être étudié.
const MaxNbSommets = ...;
type Lien = ^Sommet;
Sommet = record
v: integer; {v=numéro du sommet}
Next: Lien; { par hash-coding}
end; { Sommet }
var PremierVoisin:array[1..MaxNbSommets] of Lien;
CmptrVisite : 0..MaxNbSommets; {Nb. sommets déjà visités}
NumDOrdre : array[1..MaxNbSommets] of integer;
Nom : array[1..MaxNbSommets] of char; {noms des sommets}
Pile : array[1..MaxNbSommets] of 1..MaxNbSommets;
SommetDePile : integer;
NbSommets : 0..MaxNbSommets; {nombre de sommets}
function Visite(IndexSommet:integer) : integer;
{retourne le numéro d'ordre du sommet le
plus ancien rencontré dans le cadre du
parcours récursif des successeurs du
sommet dont l'index est passé en param.}
var Courant: Lien;
Anciennete,LePlusAncien : integer;
begin { Visite }
CmptrVisite := CmptrVisite+1;
NumDOrdre[IndexSommet] := CmptrVisite;
LePlusAncien := CmptrVisite;
Pile [SommetDePile] := IndexSommet;
SommetDePile := SommetDePile+1;
Courant:= PremierVoisin[IndexSommet];
while Courant <> nil do begin
if NumDOrdre[Courant^.v]=0 then begin
Anciennete := Visite (Courant^.v);
if Anciennete <LePlusAncien then
LePlusAncien := Anciennete;
end { then }
else if NumDOrdre[Courant^.v] < LePlusAncien then
LePlusAncien:=NumDOrdre[Courant^.v];
Courant := Courant^.Next;
end; { while }
if LePlusAncien = NumDOrdre[IndexSommet] then begin
{ on arrive ici s'il n'y a pas eu de changement dans
la boucle while, ou si l'on est revenu du traitement
récursif des suivants vers le plus ancien }
repeat
SommetDePile := SommetDePile-1;
write (Nom[Pile[SommetDePile]]);
NumDOrdre[Pile[SommetDePile]] :=NbSommets+1;
until Pile[SommetDePile]=IndexSommet;
writeln;
end; { if }
Visite := LePlusAncien;
end; { Visite }
Explication de la fonction Visite :
Pour mieux comprendre le fonctionnement de cet algorithme, il faut se rappeler que les sommets d'une composante fortement connexe font partie d'un même cycle voire de plusieurs (par exemple, dans la figure 11.1, GJL et AGC forment deux cycles faisant partie de la même composante fortement connexe). C'est donc en revenant sur un sommet déjà rencontré le long du chemin courant que l'on s'aperçoit de ces cycles et que l'on peut ainsi déterminer les composantes fortement connexes du graphe.
Comme il peut y avoir plusieurs cycles dans la même composante, la fonction Visite retourne le plus ancien des noeuds rencontrés le long d'un chemin. Cette valeur de retour n'a d'intérêt que lorsque la fonction Visite est appelée récursivement (dans la partie C).
Si la fonction Visite retourne un numéro plus ancien (plus petit) que le numéro de noeud courant, c'est que ce noeud courant fait partie d'un cycle sans en être le point de départ (c'est-à-dire que ce noeud n'est pas le plus ancien noeud de la composante à être traité).
Si la fonction Visite retourne un numéro égal au numéro de noeud courant, c'est que ce noeud courant est le point de départ d'une composante fortement connexe.
Si la fonction Visite retourne un numéro supérieur au numéro de noeud courant, c'est que ce noeud courant fait partie d'un chemin qui ne constitue pas un cycle, le noeud courant constitue donc une composante fortement connexe à lui tout seul.
Prenons pour exemple un graphe comportant deux cycles imbriqués :
En commençant le parcours par le sommet A, l'on est amené à traiter le sommet B puis le sommet C. Lors du traitement du sommet C, l'on se rend compte que C fait partie d'un cycle car le plus ancien de ses successeurs (A) a un numéro d'ordre plus petit (1) que le sien (3). On ne fera pourtant rien encore.
Après avoir traité C, l'on revient au traitement des successeurs de B. On arrive donc à D pour lequel le plus ancien successeur est C. Là encore, l'on se rend compte que D fait partie d'un cycle car le plus ancien de ses successeurs (C) a un numéro d'ordre plus petit (3) que le sien (4). On ne fera une fois de plus rien d'autre.
Le traitement des successeurs de B est terminé et le plus ancien sommet atteint est A. B fait donc aussi partie d'un cycle dont il n'est pas le point de départ. C'est en revenant au traitement des successeurs de A que l'on se rend compte que le plus ancien sommet que l'on peut atteindre depuis A est A lui-même. On a donc détecté une composante fortement connexe partant de A et comprenant B, C et D.
Bien évidemment, la fonction Visite peut faire beaucoup plus que simplement imprimer les noms des sommets d'une composante fortement connexe. Pour cela il suffit de remplacer, dans la partie E, l'instruction
write(Nom[Pile[SommetDePile]])
par l'appel à une procédure de traitement P; on obtient alors :
if LePlusAncien = NumDOrdre(IndexSommet) then
repeat
SommetDePile := SommetDePile-1;
P(Nom[Pile[SommetDePile]])
until Pile[SommetDePile] = IndexSommet;
12.
Structures récursives non linéaires: les réseaux
Site Hosting: Bronco
Table des
matières.