Parcours en largeur d'un graphe
Bonjour a vous tous, voila j'ai un probleme dans la gestion de ma file pour le parcours en largeur d'un graphe, elle n'enfile pas mes valeurs donc une fois la boucle for terminée au lieu de defiler, elle fait une erreur de seg...
Code:
1
2
3
4
5
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
21
22
23
24
25
26
27
28
29
30
31
32
33
34
35
36
37
38
39
40
41
42
43
44
45
46
47
48
49
50
51
52
53
54
55
56
57
58
59
60
61
62
63
64
65
66
67
68
69
70
71
72
73
74
75
76
77
78
79
80
81
82
83
84
85
86
87
88
89
90
91
92
93
94
95
96
97
98
99
|
/* Fichier File.c */
#define TRUE 0
#define FALSE 1
typedef struct cel
{
struct cel *Next, *Prex;
int Val;
}Cellul, *List;
typedef struct file
{
List Tete, Queue;
}file, *File;
void Enfile (File *F, int x)
{
if (*F)
{List new = AlloueCellule (x); /* Liste ptrTete */
if (!new){printf("erreur alloc memoire dans Enfile\n"); return;}
if ((*F)->Tete)
{ /* ptrTete = (*F)->Tete */
ptrTete->Next=new;
new->Prex=ptrTete;
(*F)->Tete=new;
}
else {(*F)->Tete=new; (*F)->Queue=new;}
}
return;
}
int Defile (File *F)
{
int res=0;
if (*F);
{
List ptr=NULL;
if ((*F)->Queue) /* if (((*F)->Queue->Next)!=NULL) */
{
ptr=(*F)->Queue;
res=ptr->Val;
(*F)->Queue = ptr->Next;
ptr->Prex = NULL; /* (*F)->Queue->Prex = NULL */
free(ptr);
return res;
}
if ((*F)->Queue == (*F)->Tete) /* else */
{
ptr = (*F)->Queue;
res=ptr->Val;
(*F)->Queue =NULL;
(*F)->Tete = NULL;
free (ptr);
return res;
}
}
return -1;
}
/* Fichier Graphe.c */
#define GREEN 0 /* visite non commencée */
#define YELLOW 1 /* visite commencée */
#define RED 2 /* visite terminée */
/* graphes par liste d'adjacence */
typedef struct cell
{
int Val;
struct cell* Suiv;
} Cellule,* Liste;
typedef struct graph
{
int size; /* size is the number of vertices */
Liste* adj; /* array of the adjacency lists */
int *flag; /* Bien definir comme un pointeur et non int flag[] */
}graph, *Graph; /* type Graph pointeur sur la structure */
void ParcoursLargeur (Graph g, int v)
{
initGREEN(g);
Liste w;
File F = InitFile ();
printf ("%d", v);
g->flag[v] = GREEN; /* g->flag[v] = YELLOW; */
Enfile (&F, v);
while (EstVide(F) != TRUE)
{
v=Defile (&F);
for (w=g->adj[v]; w !=NULL; w=w->Suiv)
if (g->flag[w->Val] == GREEN)
{
Enfile(&F,w->Val);
g->flag[w->Val] = YELLOW;
}printf("\n");
}
} |
Les commentaires sont une correction de mon code
