morissardj's Home Page

Home
Langage C

Langage C - Les graphes - forme liste adjacence

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

ici

Représentation par liste d'ajacence

Algorithme de parcours en largeur

Cet algorithme diffère de l'algorithme de parcours en profondeur par le fait que, à partir d'un sommet S, il liste d'abord les voisins de S pour ensuite les explorer un par un. Ce mode de fonctionnement utilise donc une file FIFO dans laquelle il prend le premier sommet et place en dernier ses voisins non encore explorés.
Si le graphe est cyclique, il faudra en outre marquer les sommets déjà visités pour que l'algorithme puisse se terminer.

Implémentation

BFS(graphe G, sommet s):
{
f=CreerFile();
Enfiler(f, s);
debut
TANT-QUE NON FileVide(f) FAIRE
   x=Défiler(f);
   Marquer(x)
   TANT-QUE ExisteFils(x) FAIRE
            z=FilsSuivant(x);
            SI NonMarqué(z) Enfiler(f, z);
   FIN-TANT-QUE
FIN-TANT-QUE
fin
}

Sur le graphe suivant, cet algorithme va alors fonctionner ainsi:

Il explore dans l'ordre les sommets A, B, C, E, D, F, G, contrairement à l'algorithme de parcours en profondeur qui cherchait dans cet ordre: A, B, D, F, E, C, G.

Algorithme de parcours en profondeur

C'est un algorithme de recherche qui progresse à partir d'un sommet S en s'appelant récursivement pour chaque sommet voisin de S.
Le nom d'algorithme en profondeur est du au fait que, contrairement à l'algorithme de parcours en largeur, il explore en fait « à fond » les chemins un par uns: pour chaque sommet, il prend le premier sommet voisin jusqu'à ce qu'un sommet n'aie plus de voisins (ou que tout ses voisins soient marqués), et revient alors au sommet père.
Si G n'est pas un arbre ou s'il y a une composante cyclique, l'algorithme pourrait tourner indéfiniment, c'est pour cela que l'on doit en outre marquer chaque sommet déjà parcouru, et ne parcourir que les sommets pas encore marqués.
Enfin, on notera qu'il est tout à fait possible de l'implémenter itérativement à l'aide d'une pile LIFO contenant les sommets à explorer: on dépile un sommet et on empile ses voisins pas encore explorés.

Implémentation

DFS (graphe G, sommet s):
{
Marquer(S);
debut
POUR CHAQUE élément sfils de Voisin(s) FAIRE
   SI NonMarqué(sfils)
    ALORS DFS(G,sfils);
   FIN-SI
FIN-POUR
fin
}

source

Cellule.h

fifo.h

fifo.c

// fifo.c

#include <stdio.h>
#include "fifo.h"

File fileVide() {
   File F;
   F = (File)malloc(sizeof(struct _file));
   if (F == NULL) printf("erreur allocation fileVide");
   F->longueur = 0;
   F->tete = F->queue = NULL;
   return(F);
}

int longueur(File F) {
   if (F == NULL)printf("file existe pas - longueur");
   return(F->longueur);
}

void enfiler(File F, typage element) {
   Cellule cellule;
   if (F == NULL) printf ("file existe pas - enfiler");

cellule = (Cellule)malloc(sizeof(struct _cellule));
   if (cellule == NULL) printf("erreur allocation memoire - enfiler");
   cellule->element = element;
   cellule->suivant = NULL;
   if (longueur(F) == 0){
      F->tete = F->queue = cellule;
   }
   else {
     F->queue->suivant = cellule;
     F->queue = cellule;
   }
   ++(F->longueur);
}

typage tete(File F) {
   if (F == NULL || longueur(F) == 0) printf(" File existe pas - tete");
   return(F->tete->element);
}

void defiler(File F) {
   Cellule cellule;

if (F == NULL || longueur(F) == 0)printf("File existe pas - defiler");
      cellule = F->tete;
   if (longueur(F) == 1)
      F->tete = F->queue = NULL;
   else
      F->tete = F->tete->suivant;
   --(F->longueur);
   free(cellule);
}

typage defilement(File F) {
   Cellule cellule;
   typage element;
   if (F == NULL || longueur(F) == 0) printf("File existe pas - defilement");
   cellule = F->tete;
   element = cellule->element;
   if (longueur(F) == 1){
      F->tete = F->queue = NULL;
   }
   else{
      F->tete = F->tete->suivant;
   }
   free(cellule);
   --(F->longueur);
   return(element);
}

void ecrireFile(File F) {
   Cellule cellule;

if (F == NULL) printf("erreur ecrireFile");
   cellule = F->tete;
   while (cellule != NULL) {
      printf("%d ", cellule->element);
      cellule = cellule->suivant;
   }
   printf("\n");
}

graphe.h

graphe.c

#include "graphe_liste.h"
#include "fifo.h"

pSommet* CreerGraphe(int taille){
  pSommet* Newgraphe = (pSommet*)malloc(taille*sizeof(pSommet));
  int i;
  for(i=0;i<taille;i++){
    Newgraphe[i]=(pSommet)malloc(sizeof(struct Sommet));
    Newgraphe[i]->valeur=i;
    Newgraphe[i]->arc=NULL;
  }
  return Newgraphe;
}

/**************************************************/
pSommet* CreerArete(pSommet* graphe,int s1,int s2,int valeur){
  if(graphe[s1]->arc==NULL){
    pArc Newarc=(pArc)malloc(sizeof(struct Arc));
    Newarc->valeur=valeur;
    Newarc->sommet=s2;
    Newarc->arc_suivant=NULL;
    graphe[s1]->arc=Newarc;
    return graphe;
  }

else{
    pArc temp=graphe[s1]->arc;
    while( !(temp->arc_suivant==NULL)){
    temp=temp->arc_suivant;
    }
     pArc Newarc=(pArc)malloc(sizeof(struct Arc));
     Newarc->valeur=valeur;
     Newarc->sommet=s2;
     Newarc->arc_suivant=NULL;

if(temp->sommet>s2){
      Newarc->arc_suivant=temp->arc_suivant;
      Newarc->sommet=temp->sommet;
      temp->sommet=s2;
      temp->arc_suivant=Newarc;
      return graphe;
     }

temp->arc_suivant=Newarc;
    return graphe;
    }
}

/**************************************************/
void affiche(pSommet* graphe, int taille){
  int i,j;
  pArc temp;

for(i=0;i<taille;i++){
    printf("le sommet %d ",graphe[i]->valeur);
    if(!(graphe[i]->arc==NULL)){
      printf("lie a  %d",graphe[i]->arc->sommet);
      temp=graphe[i]->arc;
      while(!(temp->arc_suivant==NULL)){
      temp=temp->arc_suivant;
      printf(",%d",temp->sommet);
      }
    }
  printf("\n");
  }
}

/**************************************************/
void InitialParcourLongueur(pSommet* graphe, int taille){
     /*Initialisation de la couleur des sommets*/
     /*N=Noir, deja vu.  B=Blanc a voir*/
     printf("\n***PARCOURS EN LONGUEUR***\n");
     int i;
     for(i=0;i<taille;i++){
       graphe[i]->couleur='B';
     }
     for(i=0;i<taille;i++){
       if(graphe[i]->couleur=='B'){
       printf("%d,",graphe[i]->valeur);
       graphe[i]->couleur='N';
       pArc Temparc=graphe[i]->arc;
       while(!(Temparc==NULL)){
         ParcourLongueur(graphe,Temparc->sommet,taille);
       Temparc=Temparc->arc_suivant;
       }
       }
     }
     return;
}
/****************************************************/
void ParcourLongueur(pSommet* graphe,int s, int taille){
   if(graphe[s]->couleur=='B'){
     printf("%d,",graphe[s]->valeur);
     graphe[s]->couleur='N';
     pArc Temparc=graphe[s]->arc;
     while(!(Temparc==NULL)){
       ParcourLongueur(graphe,Temparc->sommet,taille);
       Temparc=Temparc->arc_suivant;
     }
   }
   return;
}

/**************************************************/
void InitialParcourLargeur(pSommet* graphe, int taille){
     /*Initialisation de la couleur des sommets*/
     /*N=Noir, deja vu.  B=Blanc a voir*/
     printf("\n***PARCOURS EN LARGEUR***\n");
     int i=0;
     File file = fileVide();
     for(i=0;i<taille;i++){
       graphe[i]->couleur='B';
     }
     enfiler(file,0);
     while(longueur(file)){
       i=defilement(file);
       if(graphe[i]->couleur=='B'){
         pArc Temparc=graphe[i]->arc;
         if(Temparc!=NULL){
           enfiler(file,Temparc->sommet);
           while(Temparc->arc_suivant!=NULL){
             Temparc=Temparc->arc_suivant;
             enfiler(file,Temparc->sommet);
           }
         }
       printf("%d",graphe[i]->valeur);
       graphe[i]->couleur='N';
       }
     }
     printf("\n");
}

morissardj's Home Page

Langage C - Les graphes - forme liste adjacence

Définition mathématique

Représentation par liste d'ajacence

Algorithme de parcours en largeur

Implémentation

Algorithme de parcours en profondeur

Implémentation

Cellule.h

fifo.h

fifo.c

graphe.h

graphe.c

main.c