Modèles dimplantation Il existe plusieurs manières de représenter les graphes. Entre autres, sous forme graphique sous forme de listes de sommets et d'arcs

Modèles d’implantation

• Il existe plusieurs manières de représenter les graphes. • Entre autres, sous forme graphique• sous forme de listes de sommets et d'arcs.

• La représentation graphique d'un graphe n'est toutefois utilisable que par un humain et uniquement si le graphe est peu dense ou contient relativement peu de sommets.


(G1)

A B

C

D

E F

G

H

I

La description sous forme de listes de sommets et d'arcs de ce graphe.

G = (NOEUDS, ARC)

NOEUDS = {A, B, C, D, E, F, G, H, I}

ARCS = {AC, AD, BA, BB, BF, CE, CG, DA, ED, HE, HG}


Deux principales méthodes de modélisation des graphes en tant que type abstrait:

les matrices et les listes dites de connectivité ou d'adjacence.

Le choix entre elles se fera en fonction de la densité du graphe.

Par densité, on entend la proportion d'arcs effectifs par rapport au nombre maximum d'arcs possibles (NbArcs / NbSommets2).


Matrice de connectivité ou de noeuds adjacents

Une matrice de valeurs booléennes de dimension NbSommets*NbSommets pour indiquer qu'il y a

un arc entre un sommet x et un sommet y.

Cette méthode de représentation est indiquée si le graphe est dense car il faut NbSommets2

booléens pour stocker le graphe et NbSommets2 étapes

pour initialiser la matrice.


• matrice d’adjacence :

4

25

3

1

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

Matrice d’adjacence

#define NB_SOMMET 5

typedef struct{

Sommet sommets[NB_SOMMET]; BOOL arc[NB_SOMMET][NB_SOMMET];} Graphe;

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

4

25

3

1

int no;int tag;BOOL pres;char *nom;

Sommet

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5 1

1 1

1

1

1

Matrice triangulaire

4

25

3

1


Sommet#define NB_SOMMET 5

typedef struct{

Sommet sommets[NB_SOMMET]; BOOL arc[NB_SOMMET][NB_SOMMET];} Graphe;

matrice d’adjacence : (avec graphe non orienté)On peut, pour un graphe non-orienté, économiser de l'espace en ne stockant que le triangle supérieur de la matrice symétrique.Matrice triangulaire possède 1 + 2 + 3 + ... + n = [n (n+1)] / 2 éléments.On la représente dans un vecteur ayant ce même nombre d'éléments. Si on la range par ligne, alors le vecteur aura l'allure suivante :

A11 A21 A22 A31 A32 A33 A41 ... Ann

4

25

3

1


matrice d’adjacence : (avec graphe non orienté)

Matrice triangulaire. Si A11 est en position 1 (indice inférieur du vecteur), alors l'adresse de Aij est donnée par :

Adresse = A0 + ( i - 1 ) * i / 2 + j

Ainsi, la position de A42 est A0 + 8.

Des matrices symétriques, pour lesquelles Aij = Aji pour peuvent être également représentées de cette façon.

4

25

3

1


Linéarisation d’une matrice

int main(){ int *tab; int i, j, k=0;

tab=(int*)calloc(MAX_LIGNES*MAX_COLONNES,sizeof(int));

for (i=0; i<MAX_LIGNES; i++) { for (j=0; j<MAX_COLONNES; j++) set(tab, k++, i, j); }

for (i=0; i<MAX_LIGNES; i++){ for (j=0; j<MAX_COLONNES; j++) {

printf("%d ", get(tab, i, j)); }

printf("\n"); } free(tab); return 0;}

void set (int *tab, int x, int i, int j){

tab[MAX_COLONNES*i + j] = x;}

int get(int *tab, int i, int j){

return tab[MAX_COLONNES*i + j];}

Linéarisation d’une matrice triangulaire

int main(){ int *tab; int i, j, k=0; tab=(int*) calloc( MAX_LIGNES*( MAX_LIGNES+1)/2, sizeof(int)); for (i=0; i<MAX_LIGNES; i++) { for (j=0; j<=i; j++)

set(tab, k++, i, j); } for (i=0; i<MAX_LIGNES; i++) { for (j=0; j<=i; j++) {

printf("%d ", get(tab, i, j) ); }

printf("\n"); }

free(tab); return 0;}

void set (int *tab, int x, int i, int j){ tab[i*(i+1)/2 + j] = x;}

int get(int *tab, int i, int j){ return tab[i*(i+1)/2 + j];}

#include "ModeleImplantationTabInt.h"

#define OK 0#define PAM 1

TabInt initTabInt(int *err);/* ..*/

int * set (int *tab, int x, int i, int j, int *err);/* permet de placer la donnée x dans la matrice en (i, j) exactement si on aurait à faire: tab[i][j]*/

int get(int *tab, int i, int j, int *err);/* get permet de lire l'élément de matrice en (i,j) */

TabInt destroyTabInt(TabInt tab, int *err);/* */

#include <stdlib.h>

#define MAX_LIGNES 2#define MAX_COLONNES 3

typedef int * TabInt;

#include "TabInt.h"int main(){

TabInt tab;int i, j, k=0;int err;

tab= initTabInt(&err); /*tab= initTab(INT, 2, 3, &err);*/ for (i=0; i<MAX_LIGNES; i++){ for (j=0; j<MAX_COLONNES; j++)

set(tab, k++, i, j, &err);}for (i=0; i<MAX_LIGNES; i++){ for (j=0; j<MAX_COLONNES; j++)

{printf("%d ", get(tab, i, j, &err));

}printf("\n");

}tab= destroyTabInt(tab, &err);return 0;

}

4

25

3

1



typedef struct{

Sommet sommets[NB_SOMMET]; BOOL arc[15];} Graphe;


1

1 1

1 1

1

1

2

3

4

5 1

1 1

1

1

1

11 11 11

( i + 1 ) * i / 2 + j

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5 1

1 1

1

1

1


1

11

1

1

2

3

4

5 1

1

1 2 3 4 5



typedef struct{

Sommet sommets[NB_SOMMET]; BOOL * arc[NB_SOMMET];} Graphe;

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5 1

1 1

1

1

1


1

11

1

1

2

3

4

5 1

1

1 2 3 4 5

int no;int tag;BOOL pres;char *nom;BOOL *arc;

Sommet

+

#define NB_SOMMET 5

typedef struct{

Sommet sommets[NB_SOMMET]; BOOL * arc[NB_SOMMET];} Graphe;

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5 1

1 1

1

1

1


1

21

4

1

2

3

4

5 1

3



typedef struct{

Sommet sommets[NB_SOMMET]; int * arc[NB_SOMMET];} Graphe;

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5 1

1 1

1

1

1


1

21

4

1

2

3

4

5 1

3

int no;int tag;BOOL pres;char *nom;int *arc;

Sommet

+

#define NB_SOMMET 5

typedef struct{


1

1 1

1 1

1

1 2 3 4 51

2

3

4

5 1

1 1

1

1

1

Listes d’adjacence

1

21

4

1

2

3

4

5 1

3

int no;int tag;BOOL pres;char *nom;int *arc;


typedef struct{


Listes d’adjacenceA B

C

D

E FG

H

I

1

2

3

4

5

6

7

8

9

A

B

C

D

E

F

G

H

I

3

1

5

1

4

5

4

2

7

7

6

N uméro Nom Ptr. Listes des noeuds adjacents au ne noeud

typedef struct noeud{

int numSommetAdj; struct noeud* suivant;

} Noeud;

typedef struct{ int nbNoeud;

Sommet * listeNoeud;}Graphe;

int no;int tag;BOOL pres;char *nom;Noeud *arc;

Sommet

Listes d’adjacence

L'occupation mémoire d'une matrice de connectivité est inférieure à l'occupation mémoire de la liste de connectivité correspondante dès que la densité des arcs dépasse 3 %.

La structure de liste nécessite moins d'étapes d'initialisation et de traitement mais cet avantage devient de moins en moins déterminant au fur et à mesure que la densité des arcs augmente.

Il y a donc un compromis à trouver entre gain de temps et gain d’espace.

Listes croisées

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

4

25

3

1

1

2

3

4

5

1 2 3 4 5

1

1 1

1 1

1

Listes croisées

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

4

25

3

1

1

2

3

4

5

1 2 3 4 5

1

1 1

1 1

1

Listes croisées

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

4

25

3

1

1

2

3

4

5

1 2 3 4 5

1

1 1

1 1

1

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

4

25

3

1

1

2

3

4

5

1 2 3 4 5

1

1 1

1 1

1

...

Structure entièrement dynamique

1

1 1

1 1

1

1 2 3 4 51

2

3

4

5

4

25

3

1

Un modèle pour modéliser les dessertes d’une compagnie aérienne


1

2

3

4

5

1 2 3 4 5

1

1 1

1 1

1

...

typedef struct /*Modèle pour un graphe*/{

int nb_noeuds; /*Le nombre de noeuds dans le graphe*/Noeud* noeudsOrigine; /*Pointeur sur les noeuds d'origine)*/Noeud* noeudsDestination; /*Pointeur sur les noeuds de destination)*/

}Graphe;

...


typedef struct noeud /* Un noeud dans un graphe*/{

int numero; /*Le nom de la ville associée noeud*/Arete* liste_adjacence; /*La liste des arêtes adjacentes*/int status; /*Pour la recherche par contagion*/struct noeud* suivant; /*Le prochain noeud de la liste*/

}Noeud;

1

2

3

4

5

1 2 3 4 5


typedef struct Arete /*Une arête d'un graphe*/{

int numero_origine; /*Le numéro de la ville d'origine*/int numero_destination; /*Le numéro de la ville de destination*/float temps_vol; /*Pondération de l ’arête*/struct Arete* suivante1; /*Prochaine adjacence du noeud sur une rangée*/struct Arete* suivante2; /*Prochaine adjacence du noeud sur une colonne*/

}Arete;

1


On peut également envisager d'utiliser une autre structure entièrement dynamique en créant une chaîne décrivant les sommets du graphe, où chaque élément contiendrait le nom d'un sommet, un pointeur vers le sommet suivant ainsi qu'un pointeur vers une chaîne décrivant les arcs partant de ce sommet. On aurait ainsi une chaîne des sommets et, pour chaque élément de cette chaîne, une chaîne des arcs.

Cela pourrait donner la structure suivante ...



Montréal

Toronto New York

24 13

8

25

Washington

13

13

18

"Toronto"

"New York"

"Washington"

4

nbAretes 5

nbSommets

serveurs

Reseau

connexions

"Montréal"

premiere

2

Connexion

destination

13

destination

8

etat

Connexion

Reseau

NoeudChaine

Serveur

ListeDeConnexionsRéseau Internet

TP2 Automne 2005

typedef struct{ int nbAretes; /* nb de liens dans le réseau */

int nbSommets; /* nb de serveurs dans le réseau */NoeudChaine *serveurs; /* liste chaînée des serveurs*/

} Reseau; /* représente tout le réseau */

TP2 Automne 2005

typedef struct SNoeudChaine /* Liste chaînée de serveurs */{

Serveur s;struct SNoeudChaine *suivant; /* pointeur suivant */struct SNoeudChaine *precedent; /* pointeur précédent */

}NoeudChaine;

TP2 Automne 2005

typedef struct{

Etiquette etiquette; /* étiquette d’un serveur*/ListeDeConnexions connexions; /* liste de ces connexions */EtatParcours etat; /* pour les parcours */

} Serveur;

TP2 Automne 2005

typedef struct{ Connexion *premier; /* vers le début de la liste des connexions */ int card; /* le nombre d’éléments dans la liste */} ListeDeConnexions;

TP2 Automne 2005

typedef struct connexion{

NoeudChaine *destination; /* pointeur sur le serveur s2 */int charge; /* charge de l'arc s1-s2 */struct connexion *suivant; /* vers un serveur adjacent à

s1*/} Connexion ; /* Connexion entre 2 serveurs s1 et s2 par exemple*/

TP2 Automne 2005

typedef struct noeud

{

TypeEl sommet; /* l'étiquette d'un sommet */

struct noeud* suivant; /* les listes de noeuds adjacents */

} Noeud; /* le noeud typique du graphe */

typedef struct

{

int nbNoeud; /* nombre de sommets */

TypeEl * tableauSommet; /* tableau des sommets*/

Noeud** listeNoeud; /* les listes de noeuds adjacents*/

}Graphe; /* le graphe */

Laboratoire #5

2 3123

1

2 3

Laboratoire #5

typedef struct noeud{ TypeEl sommet;

struct noeud* suivan} Noeud;

typedef struct{

int nbNoeud;

TypeEl * tableauSommet;Noeud** listeNoeud;

}Graphe;

1

1

2

typedef struct nœud NœudAdjacent;

typedef struct

{

int sommet;

int status;

Bool present;

NoeudAdjacent * listeNoeud;

} TypeEl; /* un sommet du graphe */

struct noeud

{

TypeEl sommet;

struct noeud* adjacent; /* les listes de noeuds adjacents */

};

typedef struct

{




Laboratoire#5


typedef struct

{

int sommet;

int status;

Bool present;



struct noeud

{

TypeEl * sommet;


};

typedef struct

{




Laboratoire#5


typedef struct

{

int sommet;

int status;

Bool present;



struct noeud

{

TypeEl * sommet;

int cout;


};

typedef struct

{




Laboratoire#5


typedef struct

{

int sommet;

int val;

int status;

Bool present;



struct noeud

{

TypeEl * sommet;

int cout;


};

typedef struct

{




Laboratoire#5


typedef struct Tnoeud

{ int sommet;

int val;

int status;

Bool present;


struct Tnoeud * autreSommet;


struct noeud

{

TypeEl * sommet;

int cout;

struct nœud * adjacent; /* les listes de noeuds adjacents */

};

typedef struct

{

int nbNoeud; /* nombre de sommets: optionnel */

TypeEl * tableauSommet; /* liste chaînée des sommets*/

} Graphe; /* le graphe */

Laboratoire#5

typedef struct tarete TArete;

typedef struct tnoeudObjet

{

int x, y;

TArete *NoeudAdj;

struct tnoeudObjet *Suivant;

}TNoeudObjet;

struct tarete

{

TNoeudObjet *Objets;

int cout;

TArete *Suivant;

};

typedef struct

{

TNoeudObjet *ListObjets;

}Labyrinthe;

1. Écrire le modèle d’implantation2. Écrire Graphe init(int *err);3. Écrire Graphe detruireGraphe(Graphe g, int *err);

Exercice

/* Structure pour représenter le graphe */typedef struct{ Sommet *lstSommets; /* la liste des sommets du Graphe */} Graphe ;

/* Structure pour représenter un sommet du graphe */typedef struct sommet{ int etiquette; /* étiquette du Sommet */ int etat; /* état pour le parcours. 1 : Prêt , 2 : Attente , 3 : Traité */ struct sommet *smtSuivant; /*pointeur sur le prochain sommet dans la liste de

sommets du Graphe*/ Arc *lstArc; /* la liste d'adjacence du Sommet */} Sommet;

/* Structure pour la liste d'adjacence */typedef struct arc{ Sommet *smtAdj;/* pointeur sur le sommet adjacent */ struct arc *arcSuivant; /* Pointeur sur le prochaine arc*/}Arc;

Corrigétypedef struct arc Arc;typedef struct sommet Sommet;

/* Structure pour la liste d'adjacence */struct arc{ Sommet *smtAdj; /* pointeur sur le sommet adjacent */ Arc *arcSuivant; /* Pointeur sur le prochaine arc */};

/* Structure pour représenter un sommet du graphe */struct sommet{ int etiquette; /* étiquette du Sommet */ int etat; /* état pour le parcours. 1 : Prêt , 2 : Attente , 3 : Traité */ Sommet *smtSuivant; /*pointeur sur le prochain sommet dans la liste de sommets du Graphe*/ Arc *lstArc; /* la liste d'adjacence du Sommet */} ;

/* Structure pour représenter le graphe */typedef struct{ Sommet *lstSommets; /* la liste des sommets du Graphe */} Graphe ;

Documents

Modèles dimplantation Il existe plusieurs manières de représenter les graphes. Entre autres, sous forme graphique sous forme de listes de sommets et d'arcs