mardi 6 janvier 2015 :
mardi 13 janvier 2015
mardi 20 janvier 2015
mardi 27 janvier 2015
mardi 3 février 2015 :
mardi 10 février 2015 :
mardi 17 février 2015 :
mardi 3 mars 2015 :
suivant sommaire
mardi 6 janvier 2015 :
Définitions des graphes orientés
Un «graphe orienté» est constitué de «sommets» reliés par des «arcs».
Par exemple on peut considérer le graphe G₁ ayant les cinq sommets A, B, C, D et E et les sept arcs A→B, B→C, C→E, E→A, A→C, C→A et B→E.
L'arc A→B a pour «origine» A et pour «extrémité» B.
On dit auusi que B est un «successeur» de A, ou que A est un «prédécessur» ou un «antécédant» de B, ou que B est «adjacent» à A.
Les «successeurs» de A sont B et C. Son «degré sortant» est 2.
Le seul «prédécesseur» de A est E. Son «degré entrant» est 1.
Le sommet D est isolé car il n'a pas de successeur ni de prédécesseur. Son degré sortant et son degré entrant sont nuls.
Définitions des graphes non orientés
Un «graphe non orienté» est constitué de «sommets» reliés par des «arêtes».
Par exemple on peut considérer le graphe G₂ ayant les cinq sommets A, B, C, D et E et les six arêtes A↔B, B↔C, C↔E, E↔A, A↔C et B↔E.
Les deux extrémités A et B de l'arête A↔B jouent des rôles symétriques. On aurait pu la noter B↔A.
Les «voisins» de A sont B et C. Son «degré» est 2.
représentation des graphes en C
Un graphe non orienté peut être représenté comme un graphe orienté en remplaçant l'arête A↔B par les deux arcs A→B et B→A.
Donc on s'intéressera uniquement à la représentation des graphes orientés.
Il est pratique d'utiliser des tableaux dont les indices sont les sommets du graphe.
Pour simplifier, on supposera donc qu'il y a N sommets qui sont numérotés de 0 à N-1.
Par exemple dans le graphe G₁ les sommets A, B, C, D et E seront remplacés par leur numéros 0, 1, 2, 3 et 4.
Dans un vrai programme, les procédures gérant les graphes doivent pouvoir s'appliquer à des graphes de tailles variables.
Mais pour simplifier la description de ces procédures dans ce cours, on supposera le nombre de sommets nbs et le nombre d'arêtes nbs fixés.
Le programme commencera donc par
<![CDATA[#define nbs 5
#define nba 7
]]>
Dans les algorithmes sur les graphes, on a souvent des traitements à faire sur tous les successeurs d'un sommet donné.
La boucle
<![CDATA[pour tout t successeur de s faire truc(t)]]>
doit donc se traduire facilement et efficacement en C.
Il faut donc choisir une représentation des graphes adaptée.
matrice d'adjacence
Si le nombre d'arcs n'est pas négligeable devant le carré du nombre de sommets, on peut utiliser une matrice d'adjacence.
<![CDATA[typedef int graphe1[nbs][nbs];
graphe1 g1={{0, 1, 1, 0, 0},
{0, 0, 1, 0, 1},
{1, 0, 0, 0, 1},
{0, 0, 0, 0, 0},
{1, 0, 0, 0, 0}};
for(int t=0;t<N;t++) if(g1[s][t]) truc(t);
]]>
listes d'adjacence dans un tableau
<![CDATA[typedef int graphe2[nba+nbs+1];
enum {A, B, C, D, E};
graphe2 g2={/* A→ */ B, C,
/* B→ */ C, E,
/* C→ */ A, E,
/* E→ */ A,
0,2,4,6,6,7};
int *lim=g2+nba;
for(int i=lim[s];i<lim[s+1];i++) truc(g2[i]);
]]>
listes d'adjacence chaînées avec des pointeurs
<![CDATA[enum {A, B, C, D, E};
typedef struct maillon maillon, *liste, *graphe3[nbs];
struct maillon { int s; liste suite; } m1={C,0}, m2={B,&m1}, m3={E,0}, m4={C,&m3}, m5={E,0}, m6={A,&m5}, m7={A,0};
graphe3 g3={&m2,&m4,&m6,0,&m5};
for(liste p=g3[s];p;p=p->suite) truc(p->s);
]]>
liste des arcs + listes d'adjacencece chaînées avec des tableaux
<![CDATA[enum {A, B, C, D, E};
typedef int graphe4[nba*2], suite_tete[nba+nbs];
graphe4 g4={A, B, C, E, A, C, B,
B, C, E, A, C, A, E};
suite_tete suite;
void setsuite(graphe4 g4, suite_tete suite) ;
setsuite(g4,suite);
int *tete=suite+nba, *ext=g4+nba;
for(int i=tete[s];i;i=suite[i]) truc(ext[i]);
]]>
exercices
Compléter les procédures et fonctions dans le programme suivant :
<![CDATA[#include<stdio.h>
#define nba 7
typedef enum {A, B, C, D, E, nbs} sommet; // A=0, B=1, C=2, D=3, E=4, nbs=5
typedef enum {faux,vrai} bool, graphe1[nbs][nbs];
graphe1 g1={{0, 1, 1, 0, 0}, // A→B A→C
{0, 0, 1, 0, 1}, // B→C B→E
{1, 0, 0, 0, 1}, // C→A C→E
{0, 0, 0, 0, 0}, //
{1, 0, 0, 0, 0}}; // E→A
typedef int graphe2[nba+nbs+1];
graphe2 g2={/* A→ */ B, C,
/* B→ */ C, E,
/* C→ */ A, E,
/* E→ */ A,
0,2,4,6,6,7};
#define lim (g2+nba)
typedef struct maillon maillon, *liste, *graphe3[nbs];
struct maillon { sommet s; liste suite; } m1={C,0}, m2={B,&m1}, m3={E,0}, m4={C,&m3}, m5={E,0}, m6={A,&m5}, m7={A,0};
graphe3 g3={&m2,&m4,&m6,0,&m7};
typedef sommet graphe4[nba*2];
graphe4 g4={A, B, C, E, A, C, B, // origines des arcs
B, C, E, A, C, A, E}; // extrémités des arcs
#define ext (g4+nba)
typedef int suite_tete[nba+nbs];
#define tete (suite+nba)
void setsuite(graphe4 g4, suite_tete suite) {}
void affarc(sommet s, sommet t) { printf("%c->%c ",s+'A',t+'A'); }
void affg1(graphe1 g1) {}
void affg3(graphe3 g3) {}
void affg4(graphe4 g4) {}
void affg5(graphe4 g4, suite_tete suite) {}
int deg_sor1(graphe1 g1, sommet s) {}
int deg_sor2(graphe2 g2, sommet s) {}
int deg_sor3(graphe3 g3, sommet s) {}
int deg_sor4(graphe4 g4, sommet s) {}
int deg_sor5(graphe4 g4, suite_tete suite, sommet s) {}
void g1g4(graphe1 g1, graphe4 g4) {}
void g2g4(graphe2 g2, graphe4 g4) {}
void g3g4(graphe3 g3, graphe4 g4) {}
void g4g1(graphe4 g4, graphe1 g1) {}
void g4g2(graphe4 g4, graphe2 g2) {}
void g4g3(graphe4 g4, graphe3 g3, liste p) {}
int main()
{ suite_tete suite;
setsuite(g4,suite);
affg1(g1);
affg2(g2);
affg3(g3);
affg4(g4);
affg5(g4,suite);
for(sommet s=0;s<nbs;s++) printf("d°(%d)=%d ",s,deg_sor1(g1,s)); printf("\n");
for(sommet s=0;s<nbs;s++) printf("d°(%d)=%d ",s,deg_sor2(g2,s)); printf("\n");
for(sommet s=0;s<nbs;s++) printf("d°(%d)=%d ",s,deg_sor3(g3,s)); printf("\n");
for(sommet s=0;s<nbs;s++) printf("d°(%d)=%d ",s,deg_sor4(g4,s)); printf("\n");
for(sommet s=0;s<nbs;s++) printf("d°(%d)=%d ",s,deg_sor5(g4,suite,s)); printf("\n");
graphe4 h4;
g1g4(g1, h4), affg4(h4);
g2g4(g2, h4), affg4(h4);
g3g4(g3, h4), affg4(h4);
maillon p[nba];
graphe1 h1; g4g1(g4, h1); affg1(h1);
graphe2 h2; g4g2(g4, h2); affg2(h2);
graphe3 h3; g4g3(g4, h3, p); affg3(h3);
return 0;
}
]]>
suivant précédent sommaire
mardi 13 janvier 2015