Jean-Jacques BOURDIN
jj NOSPAM @ up8.edu
(enlever le NO Spam)
Graphes
L'essentiel de ce cours est présenté par Benjamin Dupont et est donc présent sur sa page de cours
/* Arbres binaires tout simplement */ #include <stdio.h> #include <stdlib.h> #include <time.h> struct noeud { int num; float val; struct noeud * sg; struct noeud * sd; } ; typedef struct noeud noeud; typedef struct noeud * arbre; void afficharbre (arbre) ; arbre ajout (arbre a, int v, float x) { arbre new; int rande; if (! a) { new = (arbre) malloc (sizeof (noeud)); new->num = v; new->val = x; new->sg = (arbre) 0; new->sd = (arbre) 0; return new; } rande = rand (); printf(" insere %d en %d avec %2d\n", v, a->num, rande %10); if (rande & 0x01) { /* on le met à gauche*/ if (! (a->sg)) { /* s’il ny a pas de fils gauche */ a->sg = (arbre) malloc (sizeof (noeud)); a->sg->num = v; a->sg->val = x; a->sg->sg = (arbre) 0; a->sg->sd = (arbre) 0; return a; } a->sg = ajout(a->sg, v, x); return a; } /* on le met donc a droite*/ if (! (a->sd)) { /* s’il ny a pas de fils droit */ a->sd = (arbre) malloc (sizeof (noeud)); a->sd->num = v; a->sd->val = x; a->sd->sg = (arbre) 0; a->sd->sd = (arbre) 0; return a; } a->sd = ajout(a->sd, v, x); return a; } arbre creation (int n) { arbre a; float x, y; x = 1.5; y = 0.21; a = (arbre) 0; /* srand(time(NULL)); */ while (n--) { a = ajout (a, n, x); printf("\n"); x += y; y += 0.06; if (x > 3.0 || x < -2.0) { y = - y; } } return a; } void afficharbre (arbre a) { if (a) { afficharbre (a->sg); printf("%d %3.2f ", a->num, a->val); afficharbre (a->sd); } } void blancs (int n) { while (n--) printf(" "); } void voisarbre (arbre a, int nbb) { if (a) { voisarbre (a->sg, nbb + 1); blancs (nbb); printf(" %2d %d %3.2f\n", nbb, a->num, a->val); voisarbre (a->sd, nbb + 1); } } int main () { int n; arbre a, b; n = 20; a = creation (n); afficharbre (a); printf("\n\n"); voisarbre (a,0); } |
typedef struct paire { int num; float val; } paire_t; typedef struct arbrebv { int nbn; paire_t * vec; } arbrebv_t; void afficharbrevec (arbrebv_t, int) ; arbrebv_t creeretremplir (int n) { /* n est le nombre de noeuds */ arbrebv_t a; int i, nbs, nbcases, num; float x, y; x = 1.5; y = 0.21; nbs = n; nbcases = (n << 1) + 1; num = nbcases; a.nbn = n; a.vec = malloc (nbcases * sizeof(paire_t)); assert (a.vec); for (i = 0; i < nbs; i++) { a.vec[i].num = num; a.vec[i].val = x; if (i & 0x01) num++; else num -= 3; x += y; y += 0.06; if (x > 3.0 || x < -2.0) y = - y; } for (i = nbs; i < nbcases; i++) { a.vec[i].num = INT_MIN; a.vec[i].val = 0.0; } return a; } void afficharbrevec (arbrebv_t a, int noeud) { int i; if (noeud > a.nbn) return; i = (noeud << 1) + 1; afficharbrevec ( a, i) ; printf("%5d %5.3f\n", a.vec[noeud].num, a.vec[noeud].val); afficharbrevec ( a, i+1) ; } |
#include <stdio.h> #include <stdlib.h> #define NBN 4 struct noeud { int nb; float val; struct noeud * fils [NBN]; } ; typedef struct noeud noeud; typedef struct noeud * arbre; typedef unsigned int uint; arbre consarb (int); arbre addarb (int, arbre); void afficharbre (arbre); void afficharb (arbre, uint); uint occur (int, arbre), occurv (float, arbre); |
#include "arb.h" float calcul (int n) { static float v = 1.0; switch (n%3) { case 0: v += 0.5; break; case 1: v += 0.5; break; case 2: v = 1.0; } return v; } arbre consarb (int n) { arbre racine, a; int i, nn; if (!n) { return NULL; } nn = n; racine = (arbre) malloc (sizeof(noeud)); racine->nb = nn; racine->val = calcul(n); for (i=0; i < NBN; i++) racine->fils[i] = NULL; while (--nn) { racine = addarb (nn, racine); } nn = n; while (--nn) { racine = addarb (nn, racine); } return racine; } arbre addarb (int n, arbre a) { arbre crt; int i, j; for (i = 0; i < NBN; i++) { if (! a->fils[i]) { crt = (arbre) malloc (sizeof(noeud)); // crt = (noeud) malloc (sizeof(noeud)); a->fils[i] = crt; crt = a->fils[i]; crt->nb = n; crt->val = calcul (n); for (j = 0; j < NBN; j++) crt->fils[j] = NULL; return a; } } a->fils[0] = addarb(n, a->fils[0]); return a; } uint yest (int n, arbre a) { uint nbf, i, k; if (! a) return (uint) 0; if (n == a->nb) return (uint) 1; for (i = 0; i < NBN ; i++) if (yest (n, a->fils[i])) return (uint) 1; return (uint) 0; } |
struct graph { int nbn; int * v; } ; typedef struct graph graph_t; |
int voir (graph_t g, int i, int j) { if (i < 0 || i >= g.nbn) return -1; if (j < 0 || j >= g.nbn) return -1; return *(g.v + j * g.nbn + i); } void placer (graph_t g, int i, int j, int val) { if (i < 0 || i >= g.nbn) return ; if (j < 0 || j >= g.nbn) return ; *(g.v + j * g.nbn + i) = val; } |
graph_t construire (int nb) { graph_t g; int nbcarre, i, num; float taux, v; nbcarre = nb * nb; g.nbn = nb; g.v = (int *) malloc (nbcarre * sizeof(int)); assert (g.v); memset (g.v, 0, (size_t) nbcarre * sizeof(int)); srand(time(NULL)); taux = 0.25; num = nb / 10; while (num > 1) { num /= 5; taux /= 3.0; } for (i = 0; i < nbcarre; i++) { v = (float) rand () / RAND_MAX; num = v > taux ? 0 : 1; *(g.v + i) = num; } return g; } |
#include <stdio.h> #include <stdlib.h> #include <assert.h> #define MAX 5 struct noeud { int n; int h; float l; float surf; struct noeud * suc [3]; } ; typedef struct noeud noeud; typedef struct noeud * tas; tas creenoeud (int nb) { tas t; t = (tas) malloc (sizeof(noeud)); assert(t); t->n = nb; t->h = nb + 4; t->l = 11.0 - (float) ((t->h) << 1); if (t->l < 0) t->l *= -1.0; t->suc[0] = (tas) 0; t->suc[1] = (tas) 0; t->suc[2] = (tas) 0; t->surf = 0.0; return t; } tas creetas () { tas t[5]; int i; for (i = 0; i < 5; i++) { t[i] = creenoeud (i); } t[0]->suc[0] = t[4]; t[0]->suc[1] = (tas) 0; t[0]->suc[2] = t[2]; t[1]->suc[0] = t[0]; t[1]->suc[2] = (tas) 0; t[1]->suc[1] = t[3]; t[2]->suc[0] = (tas) 0; t[2]->suc[1] = (tas) 0; t[2]->suc[2] = t[4]; t[3]->suc[0] = (tas) 0; t[3]->suc[1] = t[0]; t[3]->suc[2] = t[2]; t[4]->suc[0] = t[2]; t[4]->suc[1] = t[3]; t[4]->suc[2] = t[1]; return t[0]; } void goaffichetas (tas t, char boo [MAX]) { if (!t) return; if (boo [t->n]) return; printf(" %d \t %d \t %f \t%f \n", t->n, t->h, t->l, t->surf); printf(" %d \t %d", (int) ((long long int) t % 10000), (int) ((long long int) t->suc[0] % 10000)); printf(" %d \t %d \n", (int) ((long long int) t->suc[1] % 10000), (int) ((long long int) t->suc[2] % 10000)); boo[t->n] = 1; goaffichetas(t->suc[0], boo); goaffichetas(t->suc[1], boo); goaffichetas(t->suc[2], boo); } void affichetas (tas t) { char boo [MAX]; int i; for (i = 0; i < MAX; i++) boo[i] = 0; goaffichetas (t, boo); } float absf (float x) { if (x < 0.0) return - x; return x; } void remplirsurf (tas t) { if (! t) return; if (t->surf != 0.0) return; t->surf = t->h * t->l; remplirsurf (t->suc[0]); remplirsurf (t->suc[1]); remplirsurf (t->suc[2]); } int main () { tas t; t = creetas (); affichetas(t); printf("\n\n"); remplirsurf(t); affichetas(t); } |
#include <stdio.h> #include <string.h> #include <stdlib.h> #include <time.h> #include <assert.h> typedef short unsigned Shu; struct graphe { int nbs; Shu * tab; } ; typedef struct graphe graphe; graphe creegraphe (int nbs) { Shu i, j, max, num; float v, taux; graphe g; g.nbs = nbs; max = nbs * nbs; taux = 25.0; num = nbs / 10; while (num > 1) { num /= 5; taux /= 3.0; } taux /= 100.0; printf("taux %g\n", taux); g.tab = (Shu *) malloc (max * sizeof(Shu)); assert(g.tab); memset(g.tab, 0, max); srand(time(NULL)); for (num = 0, i = 0; i < nbs; i++) for (j = 0; j < nbs; j++) { v = (float) rand () / RAND_MAX; g.tab[num++] = v < taux ? 1 : 0; } return g; } void voirgraf (graphe g) { Shu i, j, nb, num; nb = g.nbs; printf("Graphe\n"); for (i = 0, num = 0; i < nb; i++) { for (j = 0; j < nb; j++) printf("%c ", g.tab[num++]? '1' : ' '); printf("\n"); } } Shu nbnonnuls (graphe g) { Shu i, j, nb, num, total; nb = g.nbs; total = 0; printf("Graphe\n"); for (i = 0, num = 0; i < nb; i++) { for (j = 0; j < nb; j++) total += g.tab[num++]; } return total; } int main () { graphe g; int nb; Shu to; nb = 10; g = creegraphe (nb); voirgraf(g); to = nbnonnuls(g); printf("Pour %d il y a %d cases non vides\n soit %f %% \n", nb, to, (to * 100.0)/(nb * nb)); nb = 50; g = creegraphe (nb); to = nbnonnuls(g); printf("Pour %d il y a %d cases non vides\n soit %f %% \n", nb, to, (to * 100.0)/(nb * nb)); nb = 500; g = creegraphe (nb); to = nbnonnuls(g); printf("Pour %d il y a %d cases non vides\n soit %f %% \n", nb, to, (to * 100.0)/(nb * nb)); } /*taux 0.25 Graphe 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 1 Graphe Pour 10 il y a 25 cases non vides soit 25.000000 % taux 0.0833333 Graphe Pour 50 il y a 212 cases non vides soit 8.480000 % taux 0.00925926 Graphe Pour 500 il y a 2333 cases non vides soit 0.933200 % */ |
graphe creegraphe (int nbs) { Shu i, j, max, num; float v, taux; graphe g; g.nbs = nbs; max = nbs * nbs; taux = 25.0; num = nbs / 10; while (num > 1) { num /= 5; taux /= 3.0; } taux /= 100.0; printf("taux %g\n", taux); g.tab = (Shu *) malloc (max * sizeof(Shu)); memset(g.tab, 0, max); srand(time(NULL)); for (num = 0, i = 0; i < nbs; i++) for (j = 0; j < nbs; j++) { v = (float) rand () / RAND_MAX; g.tab[num++] = v < taux ? (Shu) (v * 1000.) : 0; } return g; } |
La principale méthode consiste à ne pas conserver les 0, donc à conserver par exemple des triplets (départ, arrivée, poids) (ou encore (i,j,arête)).
Si le graphe n‘est pas pondéré, une simple paire suffit.
Nous avons donc une structure triplet et un vecteur de triplets.struct triplet { int i; int j; float poids; } ; typedef struct triplet triple_t; struct gramaco { int nbs; /* nombre de sommets*/ int nba; /* nombre d aretes*/ triple * ares; /* vecteur d aretes*/ } typedef struct gramaco gramaco_t; |
typedef short unsigned Shu; typedef struct noeud { int nbs; /* nombre de successeurs*/ int * succ; /* vecteur de successeurs */ float * poids; /* poids de chacune des arêtes */ } noeud_t; typedef struct grafmc { int nbs; noeud_t * node; /* vecteur des noeuds*/ } grafmc_t; |
/* nombre maximal de noeuds */ /* il faut un vecteur de tous les noeuds */ typedef struct legraf { int nbn; ptnoeud * vecnode; } legraf_t; /* structure d’un noeud */ struct noeud { int num; int nbs; struct noeud * * succ; float * poids; }; /* succ est un vecteur de pointeurs, un pointeur par successeur*/ /* poids est un vecteur de poids, un poids par successeur*/ /* si le graphe est non pondéré, on peut enlever poids*/ typedef struct noeud noeud; typedef struct noeud * ptnoeud; |
#define MAX 1000 /* nombre maximal de noeuds */ /* il faut un tableau de tous les noeuds */ struct lesnoeuds { int vu; ptnoeud ne; }; typedef struct lesnoeuds legraphe [MAX]; /* structure d’un noeud */ struct noeud { int num; struct aretes * next; }; typedef struct noeud noeud; typedef struct noeud * ptnoeud; /* structure de liste de successeurs */ struct aretes { ptnoeud pt; float poids; struct aretes * suiv; } ; typedef struct aretes aretes; typedef struct aretes * ptarete; |
-5 -4 -3 -2 -1 0 +1 +2 +3 +4 +5 0 4 4 1 0 0 3 2 1 0 1 +4 -3 -4 +5 -5 0 +1 +2 -2 -1 +3Il ne reste plus qu’à donner une représentation informatique et à faire tourner les programmes.
struct strand { Shu node; short next; }; typedef struct strand strand; struct strandgraph { Shu nbs; Shu nbstr; short * node; /* first strand*/ strand * nxt;/* node and next strand*/ } ; typedef struct strandgraph strgr; |
TP du 25/10/23
Nous avons maintenant 6 structures de graphe : La matrice complète qui a déjà été vue,Dernière mise à jour : 26/10/2023 (9h)