Parcours en profondeur dans un graphe

Tavarez59282
Messages postés
13
Date d'inscription
jeudi 28 avril 2005
Statut
Membre
Dernière intervention
20 janvier 2007
- 19 nov. 2006 à 15:42
cs_laurent1024
Messages postés
987
Date d'inscription
mardi 31 mai 2005
Statut
Membre
Dernière intervention
30 août 2012
- 20 nov. 2006 à 22:21
Bonjour j'ai un sujet de tp à realiser sur les graphes à l'aide de listes d'adjacence et j'ai un incident de segmentation dans mon code lorsque j'execute. Je vous montre mes structures dans mon en tete puis le code avec en gras la partie qui pose problème. Je vois vraiment pas d'où ca vient car pourtant j'estime mon code correct donc si vous voyez ce serait bien. Merci d'avance!

/*graphe_liste.h*/
#ifndef _GRAPHE_LISTE
#include<stdio.h>
#include<stdlib.h>
#define _GRAPHE_LISTE 1

#define BLANC 0
#define GRIS 1
#define NOIR 2

typedef int SID;
typedef struct{SID *p; int ptr;}PILE;
typedef struct maillon{
SID s;
struct maillon *suivant;
}maillon;

typedef struct{int n; maillon **listes;int *pred;
int *couleur;
int *d;
int *f; }GRAPHE;

void reservation_en_memoire(int n, GRAPHE *g);
void liberation_memoire(GRAPHE *g);
void cree_graphe_vide(GRAPHE *g);
void ajouter_connection(GRAPHE *g, SID i, SID j);
void retirer_connection(GRAPHE *g, SID i, SID j);
int est_adjacent(GRAPHE *g, SID i, SID j);
int recupere_sommet_adjacent(GRAPHE *g, SID i, SID *adj, int *nbadj);
void copie_graphe(GRAPHE *g1, GRAPHE *g2);
void lire_graphe(char *nom, GRAPHE *g);
void ecrit_graphe(GRAPHE *g, char *nom);

#endif

/*graphe_liste.c seulement la partie qui ne fonctionne pas*/

void parcours_en_profondeur_recursif(GRAPHE *g, SID s)
{  
    int i, n= g->n;int *adj,*nbadj;int date=0;int voisin;
 
  for(i=0;i<n;i++)
        g->couleur[i]=BLANC;
      
    recupere_sommet_adjacent(g,s,adj,nbadj);
                          
                         if(g->couleur[s] == BLANC)
                         {
                           g->couleur[s]=GRIS;
                           date =date+1;
                           g->d[s]= date;
                          
                           for(i=0;i<(*nbadj);i++)
                          
                           {voisin=adj[i];
                           if(g->couleur[voisin]==BLANC)
                           g->pred[voisin]=s;
                           parcours_en_profondeur_recursif(g,voisin);
                           }
                           g->couleur[s] =NOIR;
                           date=date+1;
                           g->f[s]=date;
                          
                           }
                          
                     
}

PS:c'est la même erreur à chaque fois je pense on dirait qu'il n'accepte pas que je transforme le pointeur sur couleur en tableau pourtant c comme ca qu'on fait lol donc si quelqu'un a une idée.Merci encore

4 réponses

cs_laurent1024
Messages postés
987
Date d'inscription
mardi 31 mai 2005
Statut
Membre
Dernière intervention
30 août 2012
26
19 nov. 2006 à 19:33
A chaque fois que tu utilise des pointeurs il faut vérifier que ces pointeurs ne sont pas null.
donc quand tu fait g-> il faut faire un test avant (if(g!=NULL) g-> ...) . Comme tu utilises des pointeurs pour les couleurs, il faut aussi verifier que g->coleur != NULL. Si ton programme plante sur les lignes que tu as mis en gras, c'est qu'il doit y avoir un problème lors de la reservation de la mémoire. A mon avis vu la structure de tes fonctions, la fonction reservation_en_mémoire est la fonction qui te pose probleme.
si tu fais
GRAPHE *g = NULL;
reservation_en_memoire(10, g);
je pense que ici g va toujours valoir NULL.
Car quand tu passe g, il va avoir une recopie du pointeur dans la fonction reservation_en_memoire et tu va modifier le pointeur recopié mais pas directement g.

La solution est  la suivante:
tu modifies ta fonction reservation_en_mémoire comme ca :
void reservation_en_memoire(int n, GRAPHE **g){
 // a l'interieur de la fonction tu remplace tes g par (*g)
}

Tu peux egalement faire de cette façon
 GRAPHE * reservation_en_memoire(int n) {
    // ici tu creer ton pointeur
    GRAPHE g = malloc(....)
    ...
    return g;
}
Dans ton programme principale tu fait g =reservation_en_memoire(...);

Voila j'espere que j'ai été clair
++
0