IdentifiantMot de passe
Loading...
Mot de passe oublié ?Je m'inscris ! (gratuit)
Navigation

Inscrivez-vous gratuitement
pour pouvoir participer, suivre les réponses en temps réel, voter pour les messages, poser vos propres questions et recevoir la newsletter

C Discussion :

Graphe - Parcours en largeur


Sujet :

C

Vue hybride

Message précédent Message précédent   Message suivant Message suivant
  1. #1
    Membre averti
    Profil pro
    Inscrit en
    Mai 2006
    Messages
    25
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2006
    Messages : 25
    Par défaut Graphe - Parcours en largeur
    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

  2. #2
    Membre émérite
    Profil pro
    Inscrit en
    Mars 2005
    Messages
    865
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mars 2005
    Messages : 865
    Par défaut
    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.

  3. #3
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 395
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 395
    Par défaut
    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).
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  4. #4
    Membre averti
    Profil pro
    Inscrit en
    Mai 2006
    Messages
    25
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2006
    Messages : 25
    Par défaut
    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.

  5. #5
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 395
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 395
    Par défaut
    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. */
    }
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  6. #6
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 395
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 395
    Par défaut
    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).
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  7. #7
    Membre averti
    Profil pro
    Inscrit en
    Mai 2006
    Messages
    25
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2006
    Messages : 25
    Par défaut
    Citation Envoyé par Médinoc Voir le message
    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?

  8. #8
    Expert éminent
    Avatar de Médinoc
    Homme Profil pro
    Développeur informatique
    Inscrit en
    Septembre 2005
    Messages
    27 395
    Détails du profil
    Informations personnelles :
    Sexe : Homme
    Âge : 41
    Localisation : France

    Informations professionnelles :
    Activité : Développeur informatique
    Secteur : High Tech - Éditeur de logiciels

    Informations forums :
    Inscription : Septembre 2005
    Messages : 27 395
    Par défaut
    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.
    SVP, pas de questions techniques par MP. Surtout si je ne vous ai jamais parlé avant.

    "Aw, come on, who would be so stupid as to insert a cast to make an error go away without actually fixing the error?"
    Apparently everyone.
    -- Raymond Chen.
    Traduction obligatoire: "Oh, voyons, qui serait assez stupide pour mettre un cast pour faire disparaitre un message d'erreur sans vraiment corriger l'erreur?" - Apparemment, tout le monde. -- Raymond Chen.

  9. #9
    Membre averti
    Profil pro
    Inscrit en
    Mai 2006
    Messages
    25
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Mai 2006
    Messages : 25
    Par défaut
    Citation Envoyé par Médinoc Voir le message
    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.

Discussions similaires

  1. parcours en largeur dans un graphe
    Par meenah dans le forum Débuter
    Réponses: 3
    Dernier message: 17/05/2012, 22h58
  2. LISP:parcours en largeur d'un graphe
    Par handetaker dans le forum Lisp
    Réponses: 3
    Dernier message: 18/06/2011, 19h09
  3. Parcours en largeur d'un graphe
    Par line86 dans le forum C
    Réponses: 10
    Dernier message: 30/10/2007, 13h38
  4. Parcours en largeur d'une arborescence->Vector
    Par Paniez dans le forum Algorithmes et structures de données
    Réponses: 2
    Dernier message: 07/12/2006, 22h21
  5. [Graphe][Parcours] Chaines de caractères
    Par GyZmoO dans le forum Algorithmes et structures de données
    Réponses: 18
    Dernier message: 01/06/2006, 22h38

Partager

Partager
  • Envoyer la discussion sur Viadeo
  • Envoyer la discussion sur Twitter
  • Envoyer la discussion sur Google
  • Envoyer la discussion sur Facebook
  • Envoyer la discussion sur Digg
  • Envoyer la discussion sur Delicious
  • Envoyer la discussion sur MySpace
  • Envoyer la discussion sur Yahoo