Discussion :

[meenah]

Salut.
Je galère pour faire un parcours en largeur, j'ai fait une file pour la gérer mais le programme ne s'arrête pas quand il est exécuté.Voici les fonctions et procédure BFS!

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

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
/*--------------------------------------------------------------
--procedure bfs
--------------------------------------------------------------*/
 
void procedure_bfs (sommet pivot, File * file)
{
	int res_file, vide, v_ordre, vide_1;
	sommet x;
	File *  successeurs;
 
	printf("fonction procedure");	
	res_file = enfiler(file, pivot);
	if(res_file == 1){
		pivot.marque = 1;
		vide = est_vide(file);
		while(vide == 1){
			pivot = defiler(file);
			ordre = ordre + 1;
			v_ordre = ordre;
			successeurs = remplir_succ(pivot); //renvoie les successeurs de pivot
			vide_1 = est_vide(successeurs);
			while( vide_1 == 1 ){
                   x = defiler(successeurs);
                   if(x.marque == 0){
					enfiler(file, x);
					x.marque = 1;
					vide_1 = est_vide(successeurs);
			       }
			}
		}
	}
 
}
 
/*----------------------------------------------------------
--fonction BFS
-----------------------------------------------------------*/
 
void fonction_bfs( sommet tableau[])
{
	sommet pivot;
	File *file;
	int i;
 
	printf("fonction bfs\n");
	for(i = 0; i < nbr_sommet; i ++){
		pivot = tableau[i];	
		pivot.marque = 0;	
	}
	printf("fin marque \n");
	file = creer_file();
	for(i = 0; i < nbr_sommet; i ++)
		pivot = tableau[i];
		if(pivot.marque == 0){
			procedure_bfs(pivot, file);
		}
	}
}

[LittleWhite]

Bonjour,

Il faut savoir que lorsque l'on se retrouve avec un bogue, on utilise un débogueur. Celui-ci permet de repérer facilement les problèmes, de voir leurs influences et surtout de trouver leur origine pour les corriger proprement.

Donc je vous conseille de vous munir et d'apprendre à utiliser cette perle que l'on appel le débogueur.

De plus, votre code n'est pas assez commenté. Je vous propose donc d'écrire l'algorithme et son cheminement sur papier, de commenter le code et le problème apparaitra de lui même.

Ensuite, je présume que vous gérez mal pointeurs et copie de structure. Du coup, lorsque vous modifier la marque, vous ne modifiez qu'une copie et non la marche contenue dans l'arbre. Enfin, ce n'est que mon avis, un débogueur ou des printf pourra répondre mieux que moi.

[meenah]

oui effectivement le problème vient de là: marque n'est pas modifié mais du coup je ne sais pas comment modifier sa valeur!!!pouvez vous m'orienter??

[edgarjacobs]

Pour modifier la structure pivot dans la fonction procedure_bfs, il faut lui passer l'adresse la structure, et non pas une copie de la structure, ce qui est fait dans le code.

L'appel devient donc

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

1
2
		if(pivot.marque == 0){
			procedure_bfs(&pivot, file);

La fonction procedure_bfs devient dès lors

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

void procedure_bfs (sommet *pivot, File * file)

Pour adresser les membres de pivot dans la fonction, cela devient par exemple

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

pivot->marque = 1;

Ceci a pour effet de modier l'élement marque, qui est le même que celui connu par la fonction appelante.

Attention toutefois: pivot est utilisé à de nombreux endroits dans cette fonction, il faut donc modifier toutes les lignes de code qui se rapportent à lui.

Quid, par exemple, de

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

res_file = enfiler(file, pivot);

enfiler s'attend à recevoir une variable de type sommet, pas sommet *. Soit il faut modifier la fonction enfiler, soit il faut l'appeler par

Code :

Sélectionner tout - Visualiser dans une fenêtre à part

res_file = enfiler(file, *pivot);

si enfiler n'a as besoin de modifier des élements de pivot.