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]

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]

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.