Previous Next Contents

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]; 
  }
}

æ
ç
ç
ç
ç
ç
ç
è
011000
001101
000001
000010
010000
000100
ö
÷
÷
÷
÷
÷
÷
ø
  


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:
Mi,jp =
n
S
k=1
Mi,kp-1 Mk,j
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  
  1. 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.

  2. 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.
  3. 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
 
x1
( F
 
x2
( ... F
 
xn
(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:23w 
2:436w 
3:6w
4:5w
5:2w
6:4w
  

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 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:






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:

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:

  1. 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.

  2. 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.

  3. 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).

  4. 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:

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:


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: 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  
  1. 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.

  2. 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.

  3. 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;;


Previous Next Contents