Algorithmique Avancée 2022

Graphes

1. Note
   

   L'essentiel de ce cours est présenté par Benjamin Dupont et est donc présent sur sa page de cours

2. Préparation
   1. Arbres binaires
      Commençons par une déclaration et une construction :

      /* 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); }

      Vous pouvez maintenant :
      1. Chercher le nombre de noeuds d’un tel arbre.
      2. Faire une fonction qui renvoie 1 si une valeur appartient à l’arbre.
      3. Faire une fonction qui renvoie le noeud dont la valeur est le second paramètre.
      4. Faire une fonction qui renvoie la profondeur d’un certain noeud dans l’arbre.
      5. Faire une fonction qui range l’arbre, c’est-à-dire que pour tout sommet, ses successeurs droits ont des valeurs plus petites et tous ses successeurs gauches ont des valeurs supérieures ou égales.

   2. Arbres n-aires
      Voici une déclaration (en l’occurence le fichier header) :

      #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);

      Puis une fonction permettant de remplir un tel arbre, ici, simplement quadratique.

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

3. Graphes
   
   1. Les différentes structures
      
      • matrice
      • matrice compacte
      • pour chaque sommet
        • vecteur de successeurs
        • liste de successeurs
      • structure brins
   2. Exemple simple de graphe
      Nous installons une fonction pour tester les parcours de graphe vus en cours :

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

   3. Seconde structure
      
      Voici une structure de graphe (vecteur de successeurs) dans laquelle chaque noeud a au plus trois successeurs :

      #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); }

      Que se passe-t-il si on transcrit directement la fonction remplirsurf pour chercher un élément dans le graphe, après que replirsurf ait été lancée ?
   4. Nouveaux exemples
      1. Tableau complet
         On voit ici une façon de créer un graphe avec un tableau plutôt vide, surtout quand le graphe est "grand".

         #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 % */

         Voici une nouvelle version avec un poids pour les arêtes :

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

      2. Tableau compressé
         

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

         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;

      3. Vecteur de successeurs
         Pour chaque sommet on conserve un vecteur de ses successeurs. Vous avez déjà un exemple ci-dessus, mais si on veut faire plus général (non limitation de l’arité) :

         /* 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; 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 cela*/ typedef struct noeud noeud; typedef struct noeud * ptnoeud;

      4. liste de successeurs
         Pour chaque sommet on conserve une liste de ses successeurs.

         #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. Brins
         Dernière structure présentée : le système à brins, tiré de Cori 1973.
         Principe de base, une arête n est séparée en deux parties, le brin -n et le brin +n. Un sommet est associé à un de ses brins, le "premier brin".
         Chaque brin est associé à un brin suivant (en général en tournant autour du sommet) et au numéro du sommet associé.
         Exemple :
         Sommets : 0, 1, 2, 3 et 4
         arêtes : a1: 0->3, a2: 1->2, a3: 4->1, a4: 4->0, a5: 0->1,
         Le tableau des premiers brins sera :
         noeud :0  1  2  3   4  
         brin  :-1 -2 +2 +1 -3
         Tableau des brins :
         

         -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  +3
         Il 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;
         
         
         Vous pouvez maintenant utiliser la fonction de création d’un graphe
         (matrice) pondéré, creegraphe pour faire les 20 fonctions de
         passage d'une structure à l'autre : de matrice à matrice
         compacte, de brins à liste de successeurs, etc.
         
         								 
         
         
           
         
         
         Dernière mise à jour : 25/10/2022 (15h)