Chapitre 5 Graphes
La notion de graphe est une structure combinatoire permettant de
représenter de nombreuses situations rencontrées dans des
applications faisant intervenir des mathématiques discrètes et
nécessitant une solution informatique. Circuits électriques,
réseaux de transport (ferrés, routiers, aériens), réseaux
d'ordinateurs, ordonnancement d'un ensemble de tâches sont les
principaux domaines d'application où la structure de graphe
intervient. D'un point de vue formel, il s'agit d'un ensemble de
points (sommets) et d'un ensemble d'arcs reliants des couples de
sommets. Une des premières questions que l'on se pose est de
déterminer, étant donné un graphe et deux de ses sommets, s'il
existe un chemin (suite d'arcs) qui les relie; cette question très
simple d'un point de vue mathématique pose des problèmes
d'efficacité dès que l'on souhaite la traiter à l'aide de
l'ordinateur pour des graphes comportant un très grand nombre de
sommets et d'arcs. Pour se convaincre de la difficulté du problème
il suffit de considérer le jeu d'échecs et représenter chaque
configuration de pièces sur l'échiquier comme un sommet d'un
graphe, les arcs joignent chaque configuration à celles obtenues par
un mouvement d'une seule pièce; la résolution d'un problème
d'échecs revient ainsi à trouver un ensemble de chemins menant
d'un sommet à des configurations de ``mat''. La difficulté
du jeu d'échecs provient donc de la quantité importante de sommets
du graphe que l'on doit parcourir. Des graphes plus simples comme
celui des stations du Métro Parisien donnent lieu à des
problèmes de parcours beaucoup plus facilement solubles.
Il est courant, lorsque l'on étudie les graphes, de distinguer entre
les graphes orientés dans lesquels les arcs doivent être parcourus
dans un sens déterminé (de x vers y mais pas de y vers x)
et les graphes symétriques (ou non orientés) dans lesquels les
arcs (appelés alors arêtes) peuvent être parcourus dans les deux
sens. Nous nous limitons dans ce chapitre aux graphes orientés, car
les algorithmes de parcours pour les graphes orientés s'appliquent
en particulier aux graphes symétriques : il suffit de construire à
partir d'un graphe symétrique G le graphe orienté G'
comportant pour chaque arête x,y de G deux arcs opposés, l'un
de x vers y et l'autre de y vers x.
5.1 Définitions
Dans ce paragraphe nous donnons quelques définitions sur les graphes
orientés et quelques exemples, nous nous limitons ici aux
définitions les plus utiles de façon à passer très vite aux
algorithmes.
Définition 1 Un graphe G = (X,A) est donné par un ensemble X de sommets et par un sous-ensemble A du produit cartésien X ×
X appelé ensemble des arcs de G.
Un arc a=(x,y) a pour origine le sommet x et pour extrémité le sommet y. On note
or(a) = x ; ext(a) = y
Dans la suite on suppose que tous les graphes considérés sont
finis, ainsi X et par conséquent A sont des ensembles finis. On
dit que le sommet y est un successeur de x si (x,y) Î A
, x est alors un prédécesseur de y.
Définition 2 Un chemin f du graphe G=(X,A) est une suite
finie d'arcs a1,a2,...,ap telle que:
" i, 1£ i< p or(ai+1) = ext(ai).
L'origine d'un chemin f, notée or(f) est celle de son
premier arc a1 et son extrémité, notée ext (f) est
celle de son dernier arc ap, la longueur du chemin est
égale au nombre d'arcs qui le composent, c'est-à-dire p. Un
chemin f tel que or(f)=ext(f) est appelé un circuit.
Exemple 1 Graphes de De Bruijn
Les sommets d'un tel graphe sont les suites de longueur k formées
de symboles 0 ou 1, un arc joint la suite f à la suite g si
f=xh , g=hy
où x et y sont des symboles (0 ou
1 ) et où h est une suite quelconque de k-1 symboles.
Figure 5.1 : Le graphe de De Bruijn pour k=3
Exemple 2 Graphes des diviseurs
Les sommets sont les nombres {2,3,..., n}, un arc joint p à
q si p divise q.
Figure 5.2 : Le graphe des diviseurs, n=12
5.2 Matrices d'adjacence
Une structure de données simple pour représenter un graphe est la
matrice d'adjacence M. Pour obtenir M, on numérote les sommets
du graphe de façon quelconque:
X= {x1, x2... xn }
M est une matrice carrée n × n dont les
coefficients sont 0 et 1 telle que:
Mi,j = 1 si (xi,xj) Î A,
Mi,j = 0 si (xi,xj) Ï A
Ceci donne alors les déclarations de type et de variables
suivantes:
class GrapheMat {
int m[][]; (* la matrice M d'adjacence, *)
int nb; (* n est le nombre de sommets *)
GrapheMat (int n) {
nb = n;
m = new int[n][n];
}
}
|
æ
ç
ç
ç
ç
ç
ç
è
|
0 | 1 | 1 | 0 | 0 | 0 |
0 | 0 | 1 | 1 | 0 | 1 |
0 | 0 | 0 | 0 | 0 | 1 |
0 | 0 | 0 | 0 | 1 | 0 |
0 | 1 | 0 | 0 | 0 | 0 |
0 | 0 | 0 | 1 | 0 | 0
| | |
ö
÷
÷
÷
÷
÷
÷
ø
| | | |
|
Figure 5.3 : Un exemple de graphe et sa matrice d'adjacence
Un intérêt de cette représentation est que la détermination de
chemins dans G revient au calcul des puissances successives de la
matrice M, comme le montre le théorème suivant.
Théorème 2 Soit Mp la puissance p-ième de la matrice M, le coefficient
Mi,jp est égal au nombre de chemins de longueur p de G
dont l'origine est le sommet xi et dont l'extrémité est le
sommet xj.
Preuve On effectue une récurrence sur p. Pour p=1 le
résultat est immédiat car un chemin de longueur 1 est un arc du
graphe. Le calcul de Mp, pour p > 1 donne: Or tout chemin de longueur p
entre xi et xj se décompose en un chemin de longueur p-1
entre xi et un certain xk suivi d'un arc reliant xk et xj.
Le résultat découle alors de l' hypothèse de récurrence
suivant laquelle Mi,kp-1 est le nombre de chemins de longueur
p-1 joignant xi à xk.
De ce théorème on déduit l'algorithme suivant permettant de
tester l'existence d'un chemin entre deux sommets:
static boolean existeChemin (int i, int j, GrapheMat g) {
int n = g.nb;
int m[][] = g.m;
int u[][] = copy(m);
int v[][] = copy(m);
for (int k = 1; u[i][j] == 0 && k < n; ++k) {
multiplier (v, v, m);
additionner (u, u, v);
}
return u[i][j] != 0;
}
Dans cet algorithme, les procédures multiplier(c, a, b) et additonner(c, a, b) sont respectivement des procédures qui multiplient
et ajoutent les deux matrices n × n a et b pour
obtenir la matrice c.
Remarques
- L'algorithme utilise le fait, facile à démontrer, que
l'existence d'un chemin d'origine x et d'extrémité y implique
celle d'un tel chemin ayant une longueur inférieure au nombre total
de sommets du graphe.
- Le nombre d'opérations effectuées par l'algorithme est de
l'ordre de n4 car le produit de deux matrices carrées n ×
n demande n3 opérations et l'on peut être amené à
effectuer n produits de matrices. La recherche du meilleur
algorithme possible pour le calcul du produit de deux matrices a
été très intense ces dernières années et plusieurs
améliorations de l'algorithme élémentaire demandant n3
multiplications ont été successivement trouvées, et il est rare
qu'une année se passe sans que quelqu'un n'améliore la borne.
Coppersmith et Winograd ont ainsi proposé un algorithme en
O(n2.5); mais ceci est un résultat de nature théorique car la
programmation de l'algorithme de Coppersmith et Winograd est loin
d'être aisée et l'efficacité espérée n'est atteinte que pour
des valeurs très grandes de n. Il est donc nécessaire de
construire d'autres algorithmes, faisant intervenir des notions
différentes.
- Cet algorithme construit une matrice (notée ici
u) qui peut être utilisée chaque fois que l'on veut tester
s'il existe un chemin entre deux sommets (xi et yi). Dans le cas
où on se limite à la recherche de l'existence d'un chemin entre deux
sommets donnés (et si ceci ne sera fait qu'une seule fois) on peut ne
calculer qu'une ligne de la matrice, ce qui diminue notablement la
complexité.
5.3 Fermeture transitive
La fermeture transitive d'un graphe G=(X,A) est la relation
transitive minimale contenant la relation (X,A), il s'agit d'un
graphe G*=(X,A*) tel que (x,y) Î A* si et seulement s' il
existe un chemin f dans G d'origine x et d'extrémité y.
Figure 5.4 : Un graphe et sa fermeture transitive
Le calcul de la fermeture transitive permet de répondre aux
questions concernant l'existence de chemins entre x et y dans G
et ceci pour tout couple de sommets x,y. Ce calcul complet n'est pas
vraiment utile s'il s'agit de répondre un petit nombre de fois à
des questions sur l'existence de chemins entre des couples de sommets,
on utilise alors des algorithmes qui seront décrits dans les
paragraphes suivants. Par contre lorsque l'on s'attend à avoir à
répondre de nombreuses fois à ce type de question il est
préférable de calculer au préalable (X,A*), la réponse à
chaque question est alors immédiate par simple consultation d'un des
coefficients de la matrice d'adjacence de G*. On dit que l'on
effectue un prétraitement, opération courante en
programmation dans maintes applications, ainsi le tri des éléments
d'un fichier peut aussi être considéré comme un prétraitement
en vue d'une série de consultations du fichier, le temps mis pour
trier le fichier est récupéré ensuite dans la rapidité de la
consultation. Le calcul de la fermeture transitive d'un graphe se
révèle très utile par exemple, dans certains
compilateurs-optimiseurs: un graphe est associé à chaque
procédure d'un programme, les sommets de ce graphe représentent
les variables de la procédure et un arc entre la variable a et
la variable b indique qu'une instruction de calcul de a
fait apparaître b dans son membre droit. On l'appelle
souvent graphe de dépendance. La fermeture transitive de ce
graphe donne ainsi toutes les variables nécessaires directement ou
indirectement au calcul de a; cette information est utile
lorsque l'on veut minimiser la quantité de calculs à effectuer en
machine pour l'exécution du programme.
Le calcul de (X,A*) s'effectue par itération de l'opération de
base Fx(A) qui ajoute à A les arcs (y,z) tels que y est
un prédécesseur de x et z un de ses successeurs. Plus
formellement on pose :
Fx(A) = A È {(y,z) | (y,x), (x,z) Î A }
Figure 5.5 : L'effet de l'opération Fx: les arcs ajoutés sont en pointillé
Cette opération satisfait les deux propriétés suivantes:
Proposition 1
Pour tout sommet x on a Fx(Fx(A))=Fx(A)
et pour tout
couple de sommets (x,y) : Fx(Fy(A))=Fy(Fx(A))
Preuve La première partie est très simple, on l'obtient en
remarquant que (u,x) Î Fx(A) implique (u,x) Î A et que
(x,v) Î Fx(A) implique (x,v) Î A .
Pour la seconde partie, il suffit de vérifier que si (u,v)
appartient à Fx(Fy(A)) il appartient aussi à
Fy(Fx(A)), le résultat s'obtient ensuite par raison de
symétrie. Si (u,v) Î Fx(Fy(A)) alors ou bien (u,v) Î
Fy(A) ou bien (u,x) et (x,v) Î Fy(A). Dans le premier
cas Fy(A') É Fy(A) pour tout A' É A implique
(u,v) Î Fy(Fx(A)). Dans le second cas il y a plusieurs
situations à considérer suivant que (u,x) ou (x,v)
appartiennent ou non à A; l'examen de chacune d'entre elles permet
d'obtenir le résultat. Examinons en une à titre d'exemple,
supposons que (u,x) Î A et (x,v) Ï A, comme (x,v) Î
Fy(A) on a (x,y),(y,v) Î A, ceci implique (u,y) Î Fx
(A) et (u,v) Î Fy(Fx(A))
Proposition 2 La fermeture transitive A* est donnée par :
A* = F |
| ( F |
| ( ... F |
| (A)... )) |
Preuve On se convainc facilement que A* contient
l'itérée de l'action des Fxi sur A, la partie la plus
complexe à prouver est que Fx1( Fx2( ...
Fxn(A)... )) contient A*. Pour cela on considère un
chemin joignant deux sommets x et y de G alors ce chemin
s'écrit (x,y1)(y1,y2)... (yp,y)
ainsi (x,y) Î
Fy1( Fy2( ... Fyp(A)... )) les
propriétés démontrées ci-dessus permettent d'ordonner les y
suivant leurs numéros croissants; le fait que Fy(A') É
A', pour tout A' permet ensuite de conclure.
De ces deux résultats on obtient l'algorithme suivant pour le calcul
de la fermeture transitive d'un graphe, il est en général
attribué à Roy et Warshall:
static void phi (GrapheMat g, int x) {
for (int i = 0; i < g.nb; ++i)
if (g.m[i][x] == 1)
for (int j = 0; j < g.nb; ++j)
if (g.m[x][j] == 1)
g.m[i][j] = 1;
}
static public void fermetureTransitive (GrapheMat g) {
for (int k = 0; k < g.nb; ++k)
phi(g, k);
}
Remarque L'algorithme ci-dessus effectue un nombre d'opérations que
l'on peut majorer par n3, chaque exécution de la procédure
phi pouvant nécessiter n2 opérations; cet algorithme est
donc meilleur que le calcul des puissances successives de la matrice
d'adjacence.
5.4 Listes de successeurs
Une façon plus compacte de représenter un graphe consiste à
associer à chaque sommet x la liste de ses successeurs. Ceci peut
se faire, par exemple, à l'aide d'un tableau à double indice que
l'on notera Succ. On suppose que les sommets sont numérotés de 1
à n, alors pour un sommet x et un entier i, Succ[x,i] est le
ième successeur de x. Cette représentation est utile pour obtenir
tous les successeurs d'un sommet x. Elle permet d'y accéder
en un nombre d'opérations égal au nombre d'éléments de cet
ensemble et non pas, comme c'est le cas dans la matrice d'adjacence,
au nombre total de sommets. Ainsi si dans un graphe de 20 000
sommets chaque sommet n'a que 5 successeurs l'obtention de tous les
successeurs de x se fait en consultant 4 ou 5 valeurs au lieu
des 20 000 tests à effectuer dans le cas des matrices.
L'utilisation d'un symbole supplémentaire noté w,
signifiant ``indéfini'' et n'appartenant pas à X permet une
gestion plus facile de la fin de liste. On le place à la suite de
tous les successeurs de x pour indiquer que l'on a terminé la
liste. Ainsi
Succ[x,i]=y Î X signifie que y est le ième successeur de x
Succ[x,i]=w signifie que x a i-1 successeurs.
Le graphe donné figure 5.3 plus haut admet alors
la représentation par liste de successeurs suivante:
|
1: | 2 | 3 | w | |
2: | 4 | 3 | 6 | w | |
3: | 6 | w |
4: | 5 | w |
5: | 2 | w |
6: | 4 | w |
| |
| | | |
|
Les déclarations Java correspondantes peuvent être alors les
suivantes:
class GrapheSucc{
int succ[][];
int nb;
final static int Omega = -1;
GrapheSucc (int n) {
nb = n;
succ = new int[n][n];
}
Le parcours de la liste des successeurs y d'un sommet x s'effectue
alors à l'aide de la suite d'instructions suivantes, et on retrouvera
cette suite d'instructions comme brique de base de beaucoup de
constructions d'algorithmes sur les graphes :
for (k = 0; succ[x,k] != Omega; ++k) {
int y = succ[x,k];
// Traiter y
}
On peut transformer la matrice d'adjacence d'un graphe en une
structure de liste de successeurs par l'algorithme suivant :
GrapheSucc (GrapheMat g) {
int nbMaxSucc;
nb = g.nb;
for (int i = 0; i < nb ; ++i) {
nbMaxSucc = 0;
for (int j = 0; j < nb ; ++j)
if (g.m[i][j] != 0)
nbMaxSucc = Math.max (nbMaxSucc, j);
}
succ = new int[nb][nbMaxSucc + 1];
for (int i = 0; i < nb ; ++i) {
int k = 0;
for (int j = 0; j < nb ; ++j)
if (g.m[i][j] != 0)
succ[i][k++] = j;
succ[i][k] = Omega;
}
}
Remarque La structure de liste de successeurs peut être remplacée
par une structure de liste chaînée. Cette programmation permet de gagner
en place mémoire en évitant de déclarer un nombre de successeurs
maximum pour chacun des sommets. Elle permet aussi de diminuer le
nombre d'opérations chaque fois que l'on effectue des opérations
d'ajout et de suppression de successeurs. Cette notion peut être
omise en première lecture, en particulier par ceux qui ne se sentent
pas très à l'aise dans le maniement des pointeurs. Dans toute la
suite, les algorithmes sont écrits avec la structure matricielle
succ[x,i]
. Un simple jeu de traduction permettrait de les
transformer en programmation par pointeurs; on utilise les structures
de données suivantes :
class GrapheListe{
Liste listeSucc[];
int nb;
GrapheListe (GrapheSucc g) {
nb = g.nb;
listeSucc = new Liste[g.nb];
for (int x = 0; x < g.nb ; ++x) {
listeSucc[x] = null;
for (int k = 0; g.succ[x][k] != GrapheSucc.Omega; ++k) {
int y = g.succ[x][k];
listeSucc[x] = Liste.ajouter(y, listeSucc[x]);
}
}
}
}
La transformation de la forme matricielle Succ en une structure de
liste chaînée par le constructeur de la classe donné ci dessus, on
peut noter que celui-ci inverse l'ordre dans lequel sont rangés les
successeurs d'un sommet, ceci n'a pas d'importance dans la plupart des
cas.
5.5 Arborescences
Définition 3 Une arborescence (X,A,r) de racine r est un graphe (X,A) où r
est un élément de X tel que pour tout sommet x il existe un
unique chemin d'origine r et d'extrémité x. Soit,
" x $ ! y0, y1 ,... ,yp
tels que:
y0=r, yp=x, " i, 0£ i < p
(yi,yi+1 ) Î A
L'entier p est appelé la profondeur du sommet x dans
l'arborescence. On montre facilement que dans une arborescence la
racine r n'admet pas de prédécesseur et que tout sommet y
différent de r admet un prédécesseur et un seul, ceci
implique:
|A|=|X|-1
La différence entre une arborescence et un arbre (voir
chapitre 4) est mineure. Dans un arbre, les fils d'un sommet sont
ordonnés (on distingue le fils gauche du fils droit), tel n'est pas
le cas dans une arborescence. On se sert depuis fort longtemps des
arborescences pour représenter des arbres généalogiques aussi le
vocabulaire utilisé pour les arborescences emprunte beaucoup de
termes relevant des relations familiales.
L'unique prédécesseur d'un sommet (différent de r) est
appelé son père, l'ensemble y0,y1 ,... yp-1, yp,
où p ³ 0, formant le chemin de r à x = yp est appelé
ensemble des ancêtres de x, les successeurs de x sont
aussi appelés ses fils. L'ensemble des sommets extrémités
d'un chemin d'origine x est l'ensemble des descendants de
x; il constitue une arborescence de racine x, celle-ci est l'union
de {x } et des arborescences formées des descendants des fils de
x. Pour des raisons de commodité d'écriture qui
apparaîtront dans la suite, nous adoptons la convention que tout
sommet x est à la fois ancêtre et descendant de lui-même.
Une arborescence est avantageusement représentée par le vecteur
pere qui à chaque sommet différent de la racine associe son
père. Il est souvent commode dans la programmation des algorithmes
sur les arborescences de considérer que la racine de l'arborescence
est elle-même son père, c'est la convention que nous adopterons
dans la suite.
Figure 5.6 : Une arborescence et son vecteur pere
La transformation des listes de successeurs décrivant
une arborescence en le vecteur pere s'exprime très simplement:
class Arbo {
int pere[];
final static int Omega = -1;
Arbo (GrapheSucc g, int r) {
pere = new int[g.nb];
pere[r] = r;
for (int x = 0; x < g.nb ; ++x)
for (int k = 0; g.succ[x][k] != GrapheSucc.Omega; ++k)
pere[g.succ[x][k]] = x;
}
}
Dans la suite, on suppose que l'ensemble des sommets X est l'ensemble
des entiers compris entre 1 et n, une arborescence est dite préfixe si, pour tout sommet i, l'ensemble des descendants de i
est un intervalle de l'ensemble des entiers dont le plus petit
élément est i.
Figure 5.7 : Une arborescence préfixe
Figure 5.8 : Emboitement des descendants dans une arborescence préfixe
Dans une arborescence préfixe, les intervalles de descendants
s'emboîtent les uns dans les autres comme des systèmes de
parenthèses; ainsi, si y n'est pas un descendant de x, ni x un
descendant de y, les descendants de x et de y forment des
intervalles disjoints. En revanche, si x est un ancêtre de y,
l'intervalle des descendants de y est inclus dans celui des
descendants de x.
Proposition 3 Pour toute arborescence (X,A,r) il existe une re-numérotation des
éléments de X qui la rend préfixe.
Preuve Pour trouver cette numérotation on applique
l'algorithme récursif suivant:
- La racine est numérotée 1.
- Un des fils x1 de la racine est numéroté 2.
- L'arborescence des descendants de x1 est numérotée par
appels récursifs de l'algorithme on obtient ainsi des sommets
numérotés de 2 à p1.
- Un autre fils de la racine est numéroté p1+1; les
descendants de ce fils sont numérotés récursivement de p1+1
à p2.
- On procède de même et successivement pour tous les autres
fils de la racine.
La preuve de ce que la numérotation obtenue est préfixe se fait
par récurrence sur le nombre de sommets de l'arborescence et utilise le
caractère récursif de l'algorithme.
L'algorithme qui est décrit dans la preuve ci-dessus peut s'écrire, on
suppose que l'arborescence est représentée par une matrice Succ
de successeurs la re-numérotation se fait par un vecteur numero
et r est la racine de l'arborescence.
static int[] numPrefixe (int r, GrapheSucc g) {
int numero[] = new int[g.nb];
numPrefixe1 (r, g, numero, 0);
return numero;
}
static void numPrefixe1 (int x, GrapheSucc g, int numero[], int num) {
numero[x] = num++;
for (int k = 0; g.succ[x][k] != GrapheSucc.Omega; ++k)
numPrefixe1 (g.succ[x][k], g, numero, num);
}
5.6 Arborescence des plus courts chemins.
Le parcours d'un graphe G=(X,A), c'est à dire la recherche de
chemins entre deux sommets revient au calcul de certaines arborescences
dont l'ensemble des sommets et des arcs sont inclus dans X et A
respectivement. Nous commençons par décrire celle des plus
courts chemins.
Définition 4 Dans un graphe G=(X,A), pour chaque sommet x, une arborescence des
plus courts chemins (Y,B) de racine x est une arborescence telle
que:
- Un sommet y appartient à Y si et seulement si il existe un
chemin d'origine x et d'extrémité y.
- La longueur du plus court chemin de x à y dans G est
égale à la profondeur de y dans l'arborescence (Y,B).
Figure 5.9 : Une arborescence des plus courts chemins de racine 10
L'existence de l'arborescence des plus courts chemins est une
conséquence de la remarque suivante:
Remarque Si a1,a2,..., ap est un plus court chemin entre
x=or(a1) et y=ext(ap) alors, pour tout i tel que 1£ i £ p,
a1,a2,..., ai est un plus court chemin entre x et ext(ai).
Théorème 3 Pour tout graphe G=(X,A) et tout sommet x de G il
existe une arborescence des plus courts chemins de racine x.
Preuve On considère la suite d'ensembles de sommets construite de la façon suivante:
- Y0 = {x }.
- Y1 est l'ensemble des successeurs de x, duquel il faut
éliminer x si le graphe possède un arc ayant x pour origine et
pour extrémité.
- Yi+1 est l'ensemble des successeurs d'éléments de Yi
qui n'appartiennent pas à Èk=1,i Yi.
D'autre part pour chaque Yi, i >0, on construit l'ensemble d'arcs
Bi contenant pour chaque y Î Yi un arc ayant comme
extrémité y et dont l'origine est dans Yi-1. On pose
ensuite: Y = È Yi, B = È Bi. Le graphe (Y ,B) est
alors une arborescence de par sa construction même, le fait qu'il
s'agisse de l'arborescence des plus courts chemins résulte de la
remarque ci-dessus.
La figure 5.9 donne un exemple de graphe
et une arborescence des plus courts chemins de racine 10 , celle-ci
est représentée en traits gras, les ensembles Yi et Bi sont
les suivants:
Y0 = {10 }
Y1 = {7,11 }, B1 = {(10,7), (10,11) }
Y2 = {3,9,8 }, B2 = {(7,3), (7,9), (11,8) }
Y3 = {5,6 }, B3 = {(3,5), (8,6) }
La preuve de ce théorème, comme c'est souvent le cas en
mathématiques discrètes se transforme très simplement en un
algorithme de construction de l'arborescence (Y,B).
Cet algorithme est souvent appelé algorithme de parcours en
largeur ou breadth-first search, en anglais. Nous le
décrivons ci dessous, il utilise une file avec les
primitives associées: ajout, suppression, valeur du premier, test
pour savoir si la file est vide. La file gère les ensembles Yi.
On ajoute les éléments des Yi successivement dans la file qui
contiendra donc les Yi les uns à la suite des autres. La
vérification de ce qu'un sommet n'appartient pas à
Èk=1,i Yi se fait à l'aide du prédicat (pere[y] =
omega).
static Arbo arbPlusCourt (GrapheSucc g, int x0) {
Arbo a = new Arbo(g.nb, x0);
File f = new File.vide();
File.ajouter(x0, f);
while (!File.estVide(f)) {
int x = File.valeur(f);
File.supprimer(f);
for (int k = 0; g.succ[x][k] != GrapheSucc.Omega; ++k) {
int y = g.succ[x][k];
if (a.pere[y] == Omega) {
a.pere[y] = x;
File.ajouter(y, f);
}
}
}
return a;
}
5.7 Arborescence de Trémaux
Un autre algorithme très ancien de parcours dans un graphe a été
mis au point par un ingénieur du siècle dernier, Trémaux, dont
les travaux sont cités dans un des premiers livres sur les graphes
dû à Sainte Lagüe. Son but étant de résoudre le problème de
la sortie d'un labyrinthe. Depuis l'avènement de l'informatique,
nombreux sont ceux qui ont redécouvert l'algorithme de Trémaux.
Certains en ont donné une version bien plus précise et ont montré
qu'il pouvait servir à résoudre de façon très astucieuse
beaucoup de problèmes algorithmiques sur les graphes. Il est
maintenant connu sous l'appellation de Depth-first search nom
que lui a donné un de ses brillants promoteurs: R. E. Tarjan. Ce
dernier a découvert, entre autres, le très efficace algorithme de
recherche des composantes fortement connexes que nous décrirons dans
le paragraphe suivant.
L'algorithme consiste à démarrer d'un sommet et à avancer dans
le graphe en ne repassant pas deux fois par le même sommet. Lorsque
l'on est bloqué, on ``revient sur ses pas'' jusqu'à pouvoir repartir
vers un sommet non visité. Cette opération de ``retour sur
ses pas'' est très élégamment prise en charge par l'écriture
d'une procédure récursive. Trémaux qui n'avait pas cette
possibilité à l'époque utilisait un ``fil d'Ariane'' lui
permettant de se souvenir par où il était arrivé à cet endroit
dans le labyrinthe. On peut en programmation représenter ce fil
d'Ariane par une pile.
Figure 5.10 : Exécution de l'algorithme de Trémaux
Ceci donne deux versions de l'algorithme que nous donnons ci-dessous.
static void tremauxRec (int x, GrapheSucc g, Arbo a) {
for (int k = 0; g.succ[x][k] != Omega; ++k) {
int y = g.succ[x][k];
if (a.pere[y] == Omega) {
a.pere[y] = x;
tremauxRec(y, g, a);
}
}
}
Le calcul effectif de l'arborescence de Trémaux de racine x
s'effectue en initialisant le vecteur pere
par le constructeur
de la classe des arborescences.
static Arbo tremaux (int x, GrapheSucc g) {
Arbo a = new Arbo (g.nb, x0);
tremauxRec(x0, g, a);
return a;
}
La figure 5.10 explique l'exécution de l'algorithme sur
un exemple, les appels de la procédure sont dans l'ordre:
tremauxRec(1)
tremauxRec(2)
tremauxRec(3)
tremauxRec(6)
tremauxRec(5)
tremauxRec(4)
La procédure non récursive ressemble fortement à celle du calcul
de l'arborescence des plus courts chemins à cela près que l'on
utilise une pile et non une file et que l'on enlève le sommet
courant de la pile une fois que l'on a visité tous ses successeurs.
static void tremauxPile (int x, GrapheSucc g, Arbo a) {
int y, z;
Pile p = new Pile();
Pile.ajouter (x, p);
a.pere[x] = x;
boucle:
while ( !Pile.estVide(p) ) {
y = Pile.valeur (p);
for (int k = 0; g.succ[y][k] != Omega; ++k) {
z = g.succ[y][k];
if (a.pere[z] == Omega)
a.pere[z] = y;
Pile.ajouter (z, p);
continue boucle;
}
Pile.supprimer (p);
}
}
Remarques
1 L'ensemble des sommets atteignables à partir du
sommet x est formé des sommets tels que Pere[y] ¹ Omega
à la fin de l'algorithme, on a donc un algorithme qui répond à
la question existeChemin(x,y) examinée plus haut avec un
nombre d'opérations qui est de l'ordre du nombre d'arcs du graphe
(lequel est inférieur à n2), ce qui est bien meilleur que
l'utilisation des matrices.
2 L'algorithme non récursif tel qu'il est écrit n'est pas
efficace car il lui arrive de parcourir plusieurs fois les successeurs
d'un même sommet; pour éviter cette recherche superflue, il
faudrait empiler en même temps qu'un sommet le rang du successeur
que l'on est en train de visiter et incrémenter ce rang au moment du
dépilement. Dans ce cas, on a une bien meilleure efficacité, mais
la programmation devient inélégante et le programme difficile à
lire; nous préférons de loin la version récursive.
L'ensemble des arcs du graphe G=(X,A) qui ne sont pas dans
l'arborescence de Trémaux (Y,T) de racine x est divisé en
quatre sous-ensembles:
- Les arcs dont l'origine n'est pas dans Y, ce sont les arcs
issus d'un sommet qui n'est pas atteignable à partir de x.
- Les arcs de descente, il s'agit des arcs de la forme
(y,z) où z est un descendant de y dans (Y,T), mais n'est pas un de ses successeurs dans cette arborescence.
- Les arcs de retour, il s'agit des arcs de la forme
(y,z) où z est un ancêtre de y dans (Y,T).
- Les arcs transverses, il s'agit des arcs de la forme
(y,z) où z n'est pas un ancêtre, ni un descendant de y dans
(Y,T).
On remarquera que, si (y,z) est un arc transverse, on aura rencontré
z avant y dans l'algorithme de Trémaux.
Figure 5.11 : Les arcs obtenus par Trémaux
Sur la figure 5.11, on a dessiné un graphe et les
différentes sortes d'arcs y sont représentés par des lignes
particulières. Les arcs de l'arborescence sont en traits gras, les
arcs de descente en traits normaux (sur cet exemple, il y en a deux),
les arcs dont l'origine n'est pas dans Y sont dessinés en
pointillés, de même que les arcs de retour ou transverses qui sont
munis d'une étiquette permettant de les reconnaître, celle ci est
R pour les arcs de retour et Tr pour
les arcs transverses. Les sommets ont été numérotés suivant
l'ordre dans lequel on les rencontre par l'algorithme de Trémaux,
ainsi les arcs de l'arborescence et les arcs de descente vont d'un
sommet à un sommet d'étiquette plus élevée et c'est l'inverse
pour les arcs de retour ou transverses.
5.8 Composantes fortement connexes
Dans ce paragraphe, nous donnons une application du calcul de l'arbre
de Trémaux, l'exemple a été choisi pour montrer l'utilité de
certaines constructions ingénieuses d'algorithmes sur les graphes.
La première sous-section expose le problème et donne une solution
simple mais peu efficace, les autres sous-sections décrivent
l'algorithme ingénieux de Tarjan. Il s'agit là de constructions
combinatoires qui doivent être considérées comme un complément
de lecture pour amateurs.
5.8.1 Définitions et algorithme simple
Définition 5 Soit G=(X,A) un graphe, on note ºG la relation suivante
entre sommets: x ºG y si x=y ou s'il existe un chemin
joignant x à y et un chemin joignant y à x.
Celle-ci est une relation d'équivalence. Sa définition même
entraîne la symétrie et la réflexivité. La transitivité
résulte de ce que l'on peut concaténer un chemin entre x et y
et un chemin entre y et z pour obtenir un chemin entre x et z.
Les classes de cette relation d'équivalence sont appelées les composantes fortement connexes de G. La composante fortement
connexe contenant le sommet u sera notée C(u) dans la suite.
Figure 5.12 : Composantes fortement connexes du graphe de la figure 5.11
Le graphe de la figure 5.12 comporte 5 composantes
fortement connexes, trois ne contiennent qu'un seul sommet, une est
constituée d'un triangle et la dernière comporte 9 sommets.
Lorsque la relation ºG n'a qu'une seule classe, le graphe est
dit fortement connexe. Savoir si un graphe est fortement connexe
est particulièrement important par exemple dans le choix de sens
uniques pour les voies de circulation d'un quartier.
Un algorithme de recherche des composantes fortement connexes débute
nécessairement par un parcours à partir d'un sommet x, les
sommets qui n'appartiennent pas à l'arborescence ainsi construite ne
sont certainement pas dans la composante fortement connexe de x mais
la réciproque n'est pas vraie: un sommet y qui est dans
l'arborescence issue de x n'est pas nécessairement dans sa
composante fortement connexe car il se peut qu'il n'y ait pas de
chemin allant de y à x.
Une manière simple de procéder pour le calcul de ces composantes
consiste à itérer l'algorithme suivant pour chaque sommet x dont
la composante n'a pas encore été construite:
- Déterminer les sommets extrémités de chemins d'origine x,
par exemple en utilisant l'algorithme de Trémaux à partir de x.
- Retenir parmi ceux ci les sommets qui sont l'origine d'un chemin
d'extrémité x. On peut, pour ce faire, construire le graphe
opposé de G obtenu en renversant le sens de tous les arcs de G
et appliquer l'algorithme de Trémaux sur ce graphe à partir de
x.
Cette manière de procéder est peu efficace lorsque le graphe
possède de nombreuses composantes fortement connexes, car on peut
être amené à parcourir tout le graphe autant de fois qu'il y a
de composantes. Nous allons voir dans les sections suivantes, que la
construction de l'arborescence de Trémaux issue de x va permettre
de calculer toutes les composantes connexes des sommets descendants de
x en un nombre d'opérations proportionnel au nombre d'arcs du
graphe.
5.8.2 Utilisation de l'arborescence de Trémaux
On étudie tout d'abord la numérotation des sommets d'un graphe
que l'on obtient par l'algorithme de Trémaux. On la rappelle ici
en y ajoutant une instruction de numérotation.
static int num = 0;
static void tremauxRec (int x, GrapheSucc g, Arbo a) {
numero [x] = num++;
for (int k = 0; g.succ[x][k] != Omega; ++k) {
int y = g.succ[x][k];
if (a.pere[y] == Omega) {
a.pere[y] = x;
tremauxRec(y, g, a);
}
}
}
Proposition 4 Si on numérote les sommets au fur et à mesure de leur rencontre au
cours de l'algorithme de Trémaux, on obtient une arborescence
préfixe (Y,T), un arc (u,v) qui n'est pas dans T mais dont
l'origine u et l'extrémité v sont dans Y est un arc de
descente si num(u) < num(v) et un arc de retour ou un arc transverse
si num(u) > num(v).
On supposera dans la suite que les sommets sont numérotés de cette
façon, ainsi lorsqu'on parlera du sommet i, cela voudra dire le
ième sommet rencontré lors du parcours de Trémaux et cela
évitera certaines lourdeurs d'écriture. La proposition ci-dessus
se traduit alors par le fait suivant:
Si v est un descendant de u dans (Y,T) et si un sommet w satisfait :
u £ w £ v
w est aussi un descendant de u dans cette arborescence.
Les liens entre arborescence de Trémaux (Y,T) de racine
x et les composantes fortement connexes sont dus à la proposition
suivante, que l'on énoncera après avoir donné une définition.
Définition 6 Une sous-arborescence (Y',T') de racine r' d'une arborescence
(Y,T) de racine r est constituée par des sous-ensembles Y' de
Y et T' de T formant une arborescence de racine r'.
Figure 5.13 : Un exemple de sous-arborescence
Ainsi tout élément de Y' est extrémité d'un chemin d'origine
r' et ne contenant que des arcs de T'.
Proposition 5 Soit G=(X,A) un graphe, x Î X, et (Y,T) une
arborescence de Trémaux de racine x. Pour tout sommet u de Y,
la composante fortement connexe C(u) de G contenant u est une
sous-arborescence de (Y,T).
Preuve Cette proposition contient en fait deux conclusions;
d'une part elle assure l'existence d'un sommet u0 de C(u) tel que
tous les éléments de C(u) sont des descendants de u0 dans
(Y,T), d'autre part elle affirme que pour tout v de C(u) tous
les sommets du chemin de (Y,T) joignant u0 à v sont dans
C(u).
La deuxième affirmation est simple à obtenir car dans un graphe
tout sommet situé sur un chemin joignant deux sommets appartenant
à la même composante fortement connexe est aussi dans cette
composante. Pour prouver la première assertion choisissons pour
u0 le sommet de plus petit numéro de C(u) et montrons que tout
v de C(u) est un descendant de u0 dans (Y,T). Supposons le
contraire, v étant dans la même composante que u0, il existe
un chemin f d'origine u0 et d'extrémité v. Soit w le
premier sommet de f qui n'est pas un descendant de u0 dans
(Y,T) et soit w' le sommet qui précède w dans f. L'arc
(w',w) n'est pas un arc de T, ni un arc de descente, c'est donc un
arc de retour ou un arc transverse et on a :
u0 £ w £ w'
L'arborescence (Y,T) étant préfixe on en déduit que w est
descendant de u0 d'où la contradiction cherchée.
5.8.3 Points d'attache
Une notion utile pour le calcul des composantes fortement connexe est
la notion de point d'attache dont la définition est donnée
ci-dessous. Rappelons que l'on suppose les sommets numérotés dans
l'ordre où on les rencontre par la procédure de Trémaux.
Définition 7 Etant donné un graphe G=(X,A), un sommet x de G et
l'arborescence de Trémaux (Y,T) de racine x, le point d'attache
at(y) d'un sommet y de Y est le sommet de plus petit numéro
extrémité d'un chemin de G=(X,A), d'origine y et contenant au
plus un arc (u,v) tel que u > v (c'est à dire un arc de retour
ou un arc transverse). On suppose que le chemin vide d'origine et
extrémité égale à y est un tel chemin ainsi:
at(y) £ y
On remarquera qu'un chemin qui conduit d'un sommet y à son point
d'attache est ou bien vide (le point d'attache est alors y lui
même), ou bien contient une suite d'arcs de T suivis par un arc
de retour ou un arc transverse. En effet, une succession d'arcs de T
partant de y conduit à un sommet de numéro plus grand que y,
d'autre part les arcs de descente ne sont pas utiles dans la recherche
du point d'attache, ils peuvent être remplacés par des chemins
formés d'arcs de T.
Figure 5.14 : Les points d'attaches des sommets d'un graphe
Dans la figure 5.14, on a calculé les points d'attaches
des sommets d'un graphe, ceux-ci ont été numérotés dans
l'ordre où on les rencontre dans l'algorithme de Trémaux; le point
d'attache est indiqué en petit caractère à coté du sommet en
question.
Le calcul des points d'attache se fait à l'aide d'un algorithme
récursif qui est basé sur la proposition suivante, dont la preuve
est immédiate:
Proposition 6 Le point d'attache at(y) du sommet y est le plus petit parmi les
sommets suivants:
- Le sommet y.
- Les points d'attaches des fils de y dans (Y,T).
- Les extrémités des arcs transverses ou de retour dont
l'origine est y.
L'algorithme est ainsi une adaptation de l'algorithme de Trémaux, il
calcule at[u]
en utilisant la valeur des at[v]
pour tous
les successeurs v de u.
static int pointAttache1 (int x, GrapheSucc g, int[] at) {
int y, z;
int m = x;
at[x] = x;
for (int k = 0; g.succ[x][k] != Omega; ++k) {
y = g.succ[x][k];
if (at[y] == Omega)
z = pointAttache1(y, g, at);
else
z = y;
m = Math.min(m, z);
}
at[x] = mi;
return mi;
}
static int pointAttache (int x, GrapheSucc g, int[] at) {
for (x = 0; x < g.nb; ++x)
at[x] = Omega;
at[x] = PointAttache1 (x, g, at);
}
Le calcul des composantes fortement connexes à l'aide des at(u)
est une conséquence du théorème suivant:
Théorème 4 Si u est un sommet de Y satisfaisant:
- (i) u = at(u)
- (ii) Pour tout descendant v de u dans (Y,T) on a at(v) < v
Alors, l'ensemble desc(u) des descendants de u dans (Y,T) forme
une composante fortement connexe de G.
Preuve Montrons d'abord que tout sommet de desc(u) appartient
à C(u). Soit v un sommet de desc(u), il est extrémité
d'un chemin d'origine u, prouvons que u est aussi extrémité
d'un chemin d'origine v. Si tel n'est pas le cas, on peut supposer
que v est le plus petit sommet de desc(u) à partir duquel on ne
peut atteindre u, soit f le chemin joignant v à at(v), le
chemin obtenu en concaténant f à un chemin de (Y,T) d'origine
u et d'extrémité v contient au plus un arc de retour ou
transverse ainsi:
u=at(u) £ at(v) < v
Comme (Y,T) est préfixe, at(v) appartient à
desc(u) et d'après l'hypothèse de minimalité il existe un
chemin d'origine at(v) et d'extrémité u qui concaténé à
f fournit la contradiction cherchée.
Il reste à montrer que
tout sommet w de C(u) appartient aussi à desc(u). Un tel sommet est
extrémité d'un chemin g d'origine u, nous allons voir que tout
arc dont l'origine est dans desc(u) a aussi son extrémité dans
desc(u), ainsi tous les sommets de g sont dans desc(u) et en
particulier w. Soit (v1,v2) Î A un arc tel que v1 Î
desc(u), si v2 > v1, v2 est un descendant de v1 il
appartient donc à desc(v); si v2 < v1 alors le chemin menant
de u à v2 en passant par v1 contient exactement un arc de
retour ou transverse, ainsi :
u=at(u) £ v2 < v1
et la préfixité de (Y,T) implique v2 Î desc(u).
Remarques
- Il existe toujours un sommet du graphe satisfaisant les
conditions de la proposition ci-dessus. En effet, si x est la racine
de (Y,T) on a at(x)=x. Si x satisfait (ii), alors
l'ensemble Y
en entier constitue une composante fortement connexe. Sinon il existe
un descendant y de x tel que y=at(y). En répétant cet
argument plusieurs fois et puisque le graphe est fini, on finit par
obtenir un sommet satisfaisant les deux conditions.
- La recherche des composantes fortement connexes est alors effectuée par
la détermination d'un sommet u tel que u= at(u), obtention d'une
composante égale à desc(u), suppression de tous les sommets de
desc(u) et itération des opérations précédentes jusqu'à
obtenir tout le graphe.
- Sur la figure 5.14, on peut se rendre compte du
procédé de calcul. Il y a 4 composantes fortement connexes, les
sommets u satisfaisant u = at(u) sont au nombre de 3, il s'agit
de 2, 6, 1. La première composante trouvée se compose du sommet
6 uniquement, il est supprimé et le sommet 7 devient alors tel
que u = at(u). Tous ses descendants forment une composante
fortement connexe {7,8,9}. Après leur suppression, le sommet 2
satisfait u = at(u) et il n'a plus de descendant satisfaisant la
même relation. On trouve ainsi une nouvelle composante {2,3,4,5 }.
Une fois celle-ci supprimée 1 est le seul sommet qui satisfait la
relation u = at(u) d'où la composante {1,10,11,12,13,14,15,16,17
}. Dans ce cas particulier du sommet 1, on peut atteindre tous les
sommets du graphe et le calcul s'arrête donc là; en général il
faut reconstruire une arborescence de Trémaux à partir d'un sommet
non encore atteint.
L'algorithme ci-dessous calcule en même temps at(u) pour tous les
descendants u de x et obtient successivement toutes les
composantes fortement connexes de desc(x). Il utilise le fait,
techniquement long à prouver mais guère difficile que la suppression
des descendants de u lorsque u=at(u) ne modifie pas les calculs
des at(v) en cours. La programmation donnée ici suppose que les
sommets ont déjà été numérotés par l'algorithme de Trémaux à partir de
x:
static int[] compCon (GrapheSucc g) {
int num = 0;
int numComp[] = new int[g.nb];
int at[] = new int[g.nb];
for (int x = 0; x < g.nb; ++x) {
numComp[x] = 0;
at[x] = Omega;
}
for (int x = 0; x < g.nb ; ++x)
if (numComp[x] == 0 && at[x] == Omega)
num = pointAttache1 (x, g, at, numComp, num);
return numComp;
}
static int pointAttache1 (int x, GrapheSucc g,
int at[], int numComp[], int num) {
int res = num;
at[x] = x;
for (int k = 0; g.succ[x][k] != Omega; k++) {
int y = g.succ[x][k];
if (at[y] == Omega) {
res = pointAttache1 (y, g, at, numComp, res);
if (at[x] > at[y])
at[x]= at[y];
} else
if (numComp[y] == 0)
at[x] = Math.min (at[x], y) ;
}
if (x == at[x]) {
++res;
supprimerComp(x, res, numComp, g);
}
return res;
}
static void supprimerComp (int x, int num, int[] numComp,
GrapheSucc g) {
numComp[x] = num;
for (int k = 0; g.succ[x][k] != Omega; ++k) {
int y = g.succ[x][k];
if (y > x && numComp[y] == 0)
supprimerComp (y, num, numComp, g);
}
}
5.9 Programmes en Caml
let m =
[| [| 1.0; 0.0; 0.0 |];
[| 0.0; 1.0; 0.0 |];
[| 0.0; 0.0; 1.0 |] |];;
let g =
[| [| 0; 1; 1; 0; 0; 0 |];
[| 0; 0; 1; 1; 0; 1 |];
[| 0; 0; 0; 0; 0; 1 |];
[| 0; 0; 0; 0; 1; 0 |];
[| 0; 1; 0; 0; 0; 0 |];
[| 0; 0; 0; 1; 0; 0 |] |];;
let nb_lignes m = vect_length m
and nb_colonnes m =
if vect_length m = 0 then failwith "nb_colonnes"
else vect_length m.(0);;
(* Calcule le produit des matrices a et b *)
let multiplier a b =
if nb_colonnes a <> nb_lignes b
then failwith "multiplier" else
let c =
make_matrix (nb_lignes a) (nb_colonnes b) 0 in
for i = 0 to nb_lignes a - 1 do
for j = 0 to nb_colonnes b - 1 do
let cij = ref 0 in
for k = 0 to nb_colonnes a - 1 do
cij := a.(i).(k) * b.(k).(j) + !cij;
done;
c.(i).(j) <- !cij
done
done;
c;;
(* Calcule la somme des matrices a et b *)
let ajouter a b =
if nb_colonnes a <> nb_lignes b
then failwith "ajouter" else
let c =
make_matrix (nb_lignes a) (nb_colonnes b) 0 in
for i = 0 to nb_lignes a - 1 do
for j = 0 to nb_colonnes b - 1 do
c.(i).(j) <- a.(i).(j) + b.(i).(j)
done
done;
c;;
(* Élève la matrice m à la puissance i *)
let rec puissance m i =
match i with
| 0 -> failwith "puissance"
| 1 -> m
| n -> multiplier m (puissance m (i - 1));;
let nombre_de_chemin_de_longueur n i j m =
(puissance m n).(i).(j);;
let sigma i m =
let rec pow i mp =
match i with
| 1 -> mp
| n -> ajouter mp (pow (i - 1) (multiplier m mp)) in
pow i m;;
let existe_chemin i j m =
(sigma (nb_colonnes m) m).(i).(j) <> 0;;
let phi m x =
for u = 0 to nb_colonnes m - 1 do
if m.(u).(x) = 1 then
for v = 0 to nb_colonnes m - 1 do
if m.(x).(v) = 1 then m.(u).(v) <- 1
done
done;;
let fermeture_transitive m =
let résultat =
make_matrix (nb_lignes m) (nb_colonnes m) 0 in
for i = 0 to nb_lignes m - 1 do
for j = 0 to nb_colonnes m - 1 do
résultat.(i).(j) <- m.(i).(j)
done
done;
for x = 0 to nb_colonnes m - 1 do
phi résultat x done;
résultat;;
(* Tableaux de successeurs *)
type graphe_point == (int list) vect;;
let omega = -1;;
let succ_of_mat m =
let nb_max_succ = ref 0 in
for i = 0 to nb_lignes m - 1 do
nb_max_succ := 0;
for j = 0 to nb_colonnes m - 1 do
if m.(i).(j) = 1 then
nb_max_succ := max j !nb_max_succ
done;
done;
let succ =
make_matrix (nb_lignes m) (!nb_max_succ + 1) 0 in
let k = ref 0 in
for i = 0 to nb_lignes m - 1 do
k := 0;
for j = 0 to nb_colonnes m - 1 do
if m.(i).(j) = 1 then begin
succ.(i).(!k) <- j;
incr k
end
done;
succ.(i).(!k) <- omega
done;
succ;;
(* Listes de successeurs *)
let liste_succ_of_mat m =
let gpoint = make_vect (nb_colonnes m) [] in
for i = 0 to nb_lignes m - 1 do
for j = 0 to nb_colonnes m - 1 do
if m.(i).(j) = 1
then gpoint.(i) <- j :: gpoint.(i)
done
done;
gpoint;;
let numéro = make_vect (vect_length succ) (-1);;
let num = ref (-1);;
let rec num_prefixe k = begin
incr num;
numéro.(k) <- !num;
do_list
(function x -> if numéro.(x) = -1 then
num_prefixe (x))
succ.(k)
end;;
let numPrefixe() = begin
do_vect
(function x -> if numéro.(x) = -1 then
num_prefixe (x))
numéro
end;;
let num_largeur k =
let f = file_vide() in begin
fajouter k f;
while not (fvide q) do
let k = fvaleur(f) in begin
fsupprimer f;
incr num;
numéro.(k) <- !num;
do_list
(function x -> if numéro.(x) = -1 then
begin
fajouter x f;
numéro.(x) <- 0
end)
succ.(k)
end
done
end;;
let numLargeur() = begin
do_vect
(function x -> if numéro.(x) = -1 then
num_largeur (x))
numéro
end;;
(* calcule la composante connexe
de k et retourne son point d'attache *)
let rec comp_connexe k = begin
incr num; numéro.(k) <- !num;
pajouter k p;
let min = ref !num in begin
do_list
(function x ->
let m = if numéro.(x) = -1 then
comp_connexe (x)
else
numéro.(x)
in if m < !min then
min := m)
succ.(k);
if !min = numéro.(k) then
(try while true do
printf "%d " (pvaleur(p));
numéro.(pvaleur(p)) <- max_int;
psupprimer(p);
if pvaleur(p) = k then raise Exit
done
with Exit -> printf "\n");
!min
end
end;;
let compConnexe() = begin
do_vect
(function x -> if numéro.(x) = -1 then
comp_connexe (x))
numéro
end;;