Graphe - Parcours en largeur

Version imprimable

Bonjour a tous,

Depuis hier soir j'essai de developper l'algorithme de parcours de graphe. J'ai 2 structure(liste chainée) une pour les noeud l'autre pour les arc. J'ai essayer par ce code, en commencant par le noeud 0 (int depart) cela marche pour le debut:
Ca affiche:
V[0]:0
V[1]:4
V[2]:3
V[3]:2
V[4]:6
V[5]:3
V[6]:-1

Au lieu d'afficher:
0
4
3
2
6
1
5
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 void largeur() { int depart=0; int i; int *V; Gare * garess =liste_gare; Rail * railss =liste_rail; int nbnd=image.nb_gare; V=(int *)malloc(sizeof(int)*nbnd); for(i=0;i<nbnd;i++) { V[i]=-1; } i=0; V[i]=depart; i++; while(garess->suiv!=NULL) { depart=V[i-1]; if(garess->id==depart) { Rail * railss =liste_rail; while(railss->suiv!=NULL) { if(railss->idGareDep==depart) { V[i]=railss->idGareDar; printf("V[%d]=%d\n",i,V[i]); i++; } railss=railss->suiv; } } garess=garess->suiv; } for(i=0,j=0;i<nbnd;i++,j++) { printf("V[%d]:%d\n",i,V[i]); } }
Est ce que qqun pourrait m'aider a resoudre ce probleme?

Merci d'avance

28/08/2007, 15h40
aoyou

On peut peut-être t'aider mais on ne peut pas deviner le code à ta place.

On ne connaît pas le type Gare et le type Rail (certes on pourrait deviner).
On ne sait pas ce qu'il y a dans liste_gare et liste_rail.
On ne connait pas la variable image.
28/08/2007, 15h45
Médinoc

Je ne suis pas sûr qu'on ait besoin de le savoir. Je pense surtout qu'il doit y avoir un problème quelque part dans l'algo de parcours...

Et la dernière boucle, celle qui fait l'affichage, est bizarre au niveau du for (lusiole joue avec deux variables, mais n'en utilise qu'une).

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 void largeur() { int depart=0; int i; int *V; Gare * garess =liste_gare; Rail * railss =liste_rail; int nbnd=image.nb_gare; V=(int *)malloc(sizeof(int)*nbnd); for(i=0;i<nbnd;i++) { V[i]=-1; } i=0; V[i]=depart; i++; while(garess->suiv!=NULL) { depart=V[i-1]; if(garess->id==depart) { Rail * railss =liste_rail; while(railss->suiv!=NULL) { if(railss->idGareDep==depart) { V[i]=railss->idGareDar; printf("V[%d]=%d\n",i,V[i]); i++; } railss=railss->suiv; } } garess=garess->suiv; } for(i=0;i<nbnd;i++) { printf("V[%d]:%d\n",i,V[i]); } }
Voici les structure:
typedef struct gare {
char NomVille[MaxNom];
int id;
int x;
int y;
struct gare *suiv;
} Gare;

typedef struct rail {
int idGareDep;
int idGareDar;
int xDep;
int yDep;
int xArr;
int yArr;
int longueur;
struct rail * suiv;
} Rail;

Image est une structure qui contient les données d'une image et le nb_gare et le nb_rail.

En ce qui concerne la derniére boucle, c'etait des test que j'avais fait auparevant que j'ai oublié d'enlever.

En fait le pb qui se pose c'est l'orsqu'il y a 2 gare commencant par depart il affiche les 2 mais il suit le test sur le 2eme et non le premier.

Revoici le code du premier post réindenté, avec mes commentaires.

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
void largeur()
{
	int depart=0;
	int i;
	int *V;
	/* Med: On se doute qu'il s'agit de premiers éléments de listes chainées,
	   Mais cela ne devrait pas être des variables globales, mais des paramètres. */
	Gare * garess =liste_gare;
	Rail * railss =liste_rail;
	int nbnd=image.nb_gare;
 
	V=malloc(sizeof(int)*nbnd); /* Med: En C, le cast est inutile. */
	for(i=0 ; i<nbnd ; i++)
	{
		V[i] = -1;
	}
	/* Med: Ici, tu devrais utiliser directement V[0] et i=1, ce serait plus clair */
	i=0;
	V[i]=depart;
	i++;
 
	/* Med: J'ai du mal à comprendre le noyau de cet algorithme... */
	while(garess->suiv!=NULL)
	{
		depart=V[i-1];
		if(garess->id==depart)
		{
			Rail * railss =liste_rail;
 
			while(railss->suiv!=NULL)
			{
				if(railss->idGareDep==depart)
				{
					V[i]=railss->idGareDar;
					printf("V[%d]=%d\n",i,V[i]);
					i++;
				}
				railss=railss->suiv;
			}
		}
		garess=garess->suiv;
	}
	/* Med: Boucle d'affichage trop compliquée et on ne sait pas d'où sort ton j
	   for(i=0,j=0;i<nbnd;i++,j++) */
	for(i=0 ; i<nbnd ; i++)
	{
		printf("V[%d]:%d\n",i,V[i]);
	}
	/* Med: Free absent. */
}

Après réexamen, je pense que l'algorithme n'est pas le bon.
Ce qu'il faut faire selon moi :
Code:

1 2 3 4 5 6 7 8 DECLARER Ensemble des gares vues: Liste de valeurs, l'ordre est important. Mettre la gare de départ dans les gares vues DEBUT boucle des gares vues POUR tous les rails qui partent de cette gare SI la gare d'arrivée n'est pas dans les gares vues Ajouter la gare aux gares vues (ce qui allonge la boucle) POUR toutes les gares vues Afficher la gare.
Ce qui en fait, exclut tout parcours de la liste chaînée liste_gares : On ne parcours que le vecteur V et la liste de rails.
Complexité: O(nGares*nRails), ce qui donne un O(nGares^3) au maximum (Et selon les structures mémoire employées, on doit pouvoir optimiser ça en O(nGares^2).

Citation:

Envoyé par Médinoc

Revoici le code du premier post réindenté, avec mes commentaires.

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
void largeur()
{
	int depart=0;
	int i;
	int *V;
	/* Med: On se doute qu'il s'agit de premiers éléments de listes chainées,
	   Mais cela ne devrait pas être des variables globales, mais des paramètres. */
	Gare * garess =liste_gare;
	Rail * railss =liste_rail;
	int nbnd=image.nb_gare;
 
	V=malloc(sizeof(int)*nbnd); /* Med: En C, le cast est inutile. */
	for(i=0 ; i<nbnd ; i++)
	{
		V[i] = -1;
	}
	/* Med: Ici, tu devrais utiliser directement V[0] et i=1, ce serait plus clair */
	i=0;
	V[i]=depart;
	i++;
 
	/* Med: J'ai du mal à comprendre le noyau de cet algorithme... */
	while(garess->suiv!=NULL)
	{
		depart=V[i-1];
		if(garess->id==depart)
		{
			Rail * railss =liste_rail;
 
			while(railss->suiv!=NULL)
			{
				if(railss->idGareDep==depart)
				{
					V[i]=railss->idGareDar;
					printf("V[%d]=%d\n",i,V[i]);
					i++;
				}
				railss=railss->suiv;
			}
		}
		garess=garess->suiv;
	}
	/* Med: Boucle d'affichage trop compliquée et on ne sait pas d'où sort ton j
	   for(i=0,j=0;i<nbnd;i++,j++) */
	for(i=0 ; i<nbnd ; i++)
	{
		printf("V[%d]:%d\n",i,V[i]);
	}
	/* Med: Free absent. */
}

En fait ce que j'ai voulu faire dans le noyau, c'est en gros je parcours ma liste gare, si l'id= depart alors je parcours la liste rail et dés que je trouve depart dans l'idGareDep je stocke l'idGareDar dans le tableau.

Citation:
Envoyé par Médinoc
Après réexamen, je pense que l'algorithme n'est pas le bon.
Ce qu'il faut faire selon moi :
Code:

1 2 3 4 5 6 7 8 DECLARER Ensemble des gares vues: Liste de valeurs, l'ordre est important. Mettre la gare de départ dans les gares vues DEBUT boucle des gares vues POUR tous les rails qui partent de cette gare SI la gare d'arrivée n'est pas dans les gares vues Ajouter la gare aux gares vues (ce qui allonge la boucle) POUR toutes les gares vues Afficher la gare.
Ce qui en fait, exclut tout parcours de la liste chaînée liste_gares : On ne parcours que le vecteur V et la liste de rails.
Complexité: O(nGares*nRails), ce qui donne un O(nGares^3) au maximum (Et selon les structures mémoire employées, on doit pouvoir optimiser ça en O(nGares^2).
Faudrait peut-etre utiliser les piles non?

28/08/2007, 16h15
Médinoc

Non.
Par contre, je te conseille de faire une sous-fonction qui teste si une gare est dans V (tableau des gares vues) ou non. Cette fonction prendra en paramètre V et le numéro de gare, retournera 1 ou 0 selon le cas ET NE FERA RIEN D'AUTRE.

Et c'est seulement si ça marche comme ça en O(N^3) qu'on pourra ensuite réfléchir à optimiser.

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
int recherche_visite(int * gares_visite,int num_gare)
{
int i;
	for(i=0;i<image.nb_gare;i++)
	{
		if(gares_visite[i]==num_gare)
		{
		return 0;
		}
	}
return 1;
}
 
void largeur()
{
 
/*structure rails avec premier chiffre id de depart et deuxieme chiffre id d'arrivé
0 4
5 1
5 0
0 3
3 2
3 6
1 0
1 5
6 3
2 1
 
 
*/
 
 
 
	int i=0,j;
	int *valeur;
	int * gares_visite;
	int depart=0;
	int nbnd=image.nb_gare;
	int tmp;
	int res_test;
        /*sans le cast chez moi ca marche pas*/
	valeur=(int *)malloc(sizeof(int)*nbnd);
	gares_visite=(int *)malloc(sizeof(int)*nbnd);
	for(j=0;j<=nbnd;j++)
	{
	    gares_visite[i]=depart;
	    Rail * railss =liste_rail;
	    while(railss->suiv!=NULL)
	{
		if(railss->idGareDep==depart)
		{
		tmp=railss->idGareDar;
		res_test=recherche_visite(gares_visite,tmp);
		if(res_test==1)
		{
		++i;
		gares_visite[i]=tmp;
		}
		V[i]=railss->idGareDar;
		}		
	railss=railss->suiv;	
	}
	depart=tmp;
	}
	for(i=0;i<nbnd;i++)
	{
	printf("visite[%d]=%d\n",i,gares_visite[i]);
	}

J'ai reessayer encore jusqu'a 4h du mat quand meme mais cela ne marche tjrs pas cela marche que pour les 3 premier sommet.
Si on tombe sur une gare de depart ayant 2 gare d'arrivé, tmp vaut la 2eme gare d'arriver donc cela ne suivra pas le chemin de la premiére gare d'arrivé...
Je sait pas si je suis claire...

Je sait vraiment pas comment faire....

29/08/2007, 11h12
Médinoc
1. J'ai déjà dit que le cast du retour de malloc() était inutile en C.
2. Ta fonction de recherche est erronée : Elle ne prend pas en compte le nombre de gares dans le vecteur (qui n'est pas initialisé).
  De plus, ton choix de valeur de retour est contraire au bon sens (généralement, on donne une valeur différente de zéro pour "trouvé" et une valeur nulle pour "non-trouvé")...
3. Il faudra bien qu'un jour tu te débarrasses de toutes ces variables globales...
En bonus, une fonction de recherche corrigée:
Code:

1 2 3 4 5 6 7 8 9 10 int EstGareDansListe(int const * gares, size_t nGares, int numGare) { size_t i; for(i=0 ; i<nGares ; i++) { if(gares[i] == numGare) return 1; } return 0; }
Et avec ça, tu peux faire:
Code:

1 2 3 4 if( !EstGareDansListe(garesVues, iGareVue, pRail->idGareDar) ) { /* Ajouter la gare aux gares vues... */ }

A la limite, on peut encore améliorer le code de Médinoc par
Code:

1 2 3 4 5 6 7 8 9 10 int EstGareDansListe(int const * gares, size_t nGares, int numGare) { size_t i; for(i=0 ; i<nGares ; i++) { if(gares[i] == numGare) return i; } return -1; }
Comme celà on connait l'emplacement dans le tableau, ça peut être utile.

29/08/2007, 14h12
Médinoc

Mais je ne l'ai pas mis justement parce que je ne voulais pas :

Citation:

Envoyé par Médinoc

Cette fonction prendra en paramètre V et le numéro de gare, retournera 1 ou 0 selon le cas ET NE FERA RIEN D'AUTRE.

On n'a pas besoin de savoir où est la gare, on veut juste savoir si elle est dans la liste.

De plus, le nom est dorénavant incorrect (renommer en "cherche", et on ne peut plus utiliser la fonction directement dans le test (il faut rajouter un >= 0)...
29/08/2007, 14h43
Trap D

Oui, si les spécifications de la fonctions sont telles que tu l'as dit, mais quelques fois, qui peut le plus peut le moins, et au prix de peu de changements on peut améliorer l'utitilité de la fonction.
Je conçois que dans ce cas, ça se discute.

Bonjour,
voici un pseudo-code de parcours en largeur d'un graphe, on dit BFS pour Breadth First Search :
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 Entrées : G(X, U) : le graphe a, b : deux noeuds Sorties : pred(.) : une fonction indiquant par quel arc on arrive à un noeud donné à partir de 'a'. Variables intermédiaires : X' : un sous-ensemble de noeuds. accessible(.) : fonction indiquant si un noeud est accessible à partir de 'a'. Début Pour tout x appartenant à X faire accessible(x) := faux; pred(x) := nil; FinPour X' := {a}; accessible(a) := vrai; Tant que X' <> {} et non accessible(b) faire choisir x appartenant à X'; X' := X' - {x}; Pour tout u = (x; y) appartenant à U faire Si non accessible(y) alors X' := X' U {y}; Pred(y) := (x; y); accessible(y) := vrai; FinSi FinPour FinTq Fin
juste un petit rappel mnémonique :
- Parcours d'un graphe en Profondeur : on utilise une Pile,
- Parcours d'un graphe en Largeur : on utilise une File.
J'espère qu'il vous sera utile.
Cordialement.