parcours en profondeur dans un graphe

Question

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 #include #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;icouleur[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

cs_laurent1024 · Answer

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
++

Tavarez59282 · Answer

Le probleme c'est qu'on nous a donné des types prédefinis donc logiquement ils ont pas de problème. De plus toutes les autres fonctions que j'ai créées s'executent correctement sans probleme de pointeurs. Donc je veux bien te croire et ca a l'air pertinent mais je ne peux pas modifier mes types donc soit ca vient d'ailleurs soit je ne comprend pas tout. Merci de ton aide

cs_louis14 · Answer

dans ce cas il faudrait voir ce qu'il y a dans réservation mémoire et est-ce que cette fonction est appelée avant l'utilisation de ta fonction

louis14

cs_laurent1024 · Answer

Il faut que tu essaye de debugger, en y allant étape par étape. A chaque fois que tu as un pointeur regarde sur quoi il pointeut et quand tu utilise un acces type tableau (couleur[i] par exemple) véfier que tu dépasse pas l'intervalle [0...tailledutableau-1]. Avec le code que tu as fournis j'arrive pas a voir d'ou peut provenir ton erreur.


++

Parcours en profondeur dans un graphe

4 réponses

Votre réponse

Discussions similaires