parcours en largeur dans un graphe

Version imprimable

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:

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);
		}
	}
}

17/05/2012, 13h09
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.
17/05/2012, 18h09
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??:P
17/05/2012, 22h58
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:

1 2 if(pivot.marque == 0){ procedure_bfs(&pivot, file);
La fonction procedure_bfs devient dès lors

Code:

void procedure_bfs (sommet *pivot, File * file)

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

Code:

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:

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:

res_file = enfiler(file, *pivot);

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