morissardj's Home Page

Langage C - Les graphes - forme matricielle

Deux types de structures de données sont nécessaires pour traiter de façon agréable le problème : les graphes, qui sont une représentation instinctive et mathématique des réseaux considérés, et les files, qui organisent les éléments d'un ensemble muni d'une relation d'ordre et qui permettront de comparer rapidement les longueurs d'un ensemble de chemins.

Définition mathématique

Un graphe est la donnée d'un quadruplé {S,A,X,F} avec:

S un ensemble fini non vide des sommets du graphe (les points)
A une partie de SxS dont les éléments forment les arêtes du graphe (les liaisons)
X un ensemble quelconque, fini ou non, qui détermine les poids possibles des arêtes
F la fonction de valuation du graphe qui à chaque arête associe son poids

Schématiquement, voici une représentation classique d'un graphe :

Représentation matricielle

On définit un graphe comme sa matrice des transitions (en convenant d'un symbole, dans notre cas 0, lorsque l'arête n'existe pas).
Les calculs à effectuer sur le graphe sont alors extrêmement simples : (i,j) est le poids de l'arête qui relie le sommet i au sommet j. L'inconvénient majeur de ce type de structure de données, c'est qu'elle tient une place mémoire considérable. En fait, pour coder un graphe avec O(n) de données, on utilise une place mémoire en O(n²) puisqu'on est obligé de coder toutes les arêtes, qu'elles existent ou non, une matrice est par définition statique, la taille étant fixée une bonne fois pour toutes à l'initialisation.

L'implémentation proposée alloue en fait O(n²)*2 car je créé une matrice avec les points des arêtes dans un tableau et dans l'autre un bouleen qui va dire si oui ou non l'arête existe.

source

Graphe_matrice.h

Graphe_matrice.c

#include "graphe_matrice.h"

/******************************************************
creer le graphe conciste juste a allouer la mémeoire
a tout les elements qui le composent
*/
pGraphe creer_graphe(int taille){
        pGraphe Graphe=(pGraphe)malloc(sizeof(struct Graphe));
        int i,j;
        Graphe->Valeur=(int**)malloc(taille*sizeof(int*));
        Graphe->Existe=(char**)malloc(taille*sizeof(char*));

for(i=0;i<taille;i++){
          Graphe->Valeur[i]=(int*)malloc(taille*sizeof(int));
          Graphe->Existe[i]=(char*)malloc(taille*sizeof(char));

for(j=0;j<taille;j++){
            Graphe->Existe[i][j]='F';
          }
        }

return Graphe;
}

/*******************************************************/
pGraphe creer_arete(pGraphe Graphe,int s1,int s2,int valeur){
        Graphe->Valeur[s1][s2]=valeur;
        Graphe->Existe[s1][s2]='T';
return Graphe;
}

/*******************************************************/

void afficher_liens(pGraphe Graphe, int taille){
     int i,j;

for(i=0;i<taille;i++){
     printf("somment %d est lie a ",i);
       for(j=0;j<taille;j++){
         if(Graphe->Existe[i][j]=='T')printf("%d,",j);
       }
       printf("\n");
     }
}