Discussion :

[lusiole]

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 :

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

[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.

[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).

[lusiole]

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

[Médinoc]

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

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
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. */
}

[Médinoc]

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

Code X :

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

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).

[lusiole]

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

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

[lusiole]

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

Code X :

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

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?

[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.

[lusiole]

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

[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 :

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

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 :

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

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

[Trap D]

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

Code :

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

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.

[Médinoc]

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

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)...

[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.

[sidahmed]

Bonjour,
voici un pseudo-code de parcours en largeur d'un graphe, on dit BFS pour Breadth First Search :

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