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 :

question sur les graphe en C


Sujet :

C

  1. #1
    Membre à l'essai
    Inscrit en
    Juillet 2006
    Messages
    18
    Détails du profil
    Informations forums :
    Inscription : Juillet 2006
    Messages : 18
    Points : 12
    Points
    12
    Par défaut question sur les graphe en C
    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
     
    #ifndef _GRAPHE__H
    #define _GRAPHE__H
     
     
    #include "CodesErreur.h"
     
    typedef enum {Pret, Attente, Visite} EtatNd; /*Pret: ville non encore visitée. Attente: ville a été enfilée. Visite: ville a été visitée*/
     
    typedef struct TNoeud Ville;		/*Pour representer un noeud dans un graphe*/
    typedef struct TArete Ligne;		/*Pour representer une arete d'un graphe*/
     
    typedef Ville VilleOrig;
    typedef Ville VilleDest;
     
    struct TArete					/*Pour representer une arete d'un graphe*/
    {
    	VilleOrig *ptrVilleOrig;	/*Un pointeur sur la ville d'origine*/
    	VilleDest *ptrVilleDest;	/*Un pointeur sur la ville de destination*/
    	double tempsVol;	/*Le temps du vol (en heures) entre les deux villes reliées par l'arete*/
    	struct TArete *suivDest;	/*La prochaine adjacence du noeud (sur une rangée)*/
    	struct TArete *suivOrig;	/*La prochaine adjacence du noeud (sur une colonne)*/
    };
     
    struct TNoeud			/*Pour representer un noeud dans un graphe*/
    {
    	int numero;					/*Le nom de la ville representee par le noeud*/
    	Ligne *listeAretes;	/*La liste des aretes entre le noeud et les noeuds qui lui sont adjacents*/
    	EtatNd etat;			/*L'état du noeud (pour la recherche par contagion)*/
    	struct TNoeud *precedent;	/*Le noeud précédent de la liste*/
    	struct TNoeud *suivant;		/*Le prochain noeud de la liste*/
    };
     
    typedef struct			/*Pour representer un graphe, ainsi que toutes les infos necessaires*/
    {
    	int nbNoeuds;				/*Le nombre de noeuds qui constituent le graphe*/
    	VilleOrig *vOrig;			/*Pointeur sur les noeuds du graphe (noeuds d'origine)*/
    	VilleDest *vDest;			/*Pointeur sur les noeuds du graphe (noeuds de destination)*/
    } Graphe;
     
    #endif
    commant je peux vérifier s'il est possible d'etablir un chemain entre la vile origine et la ville destination
    le protot de la fonction
    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
     
    Bool chemainExiste(Graphe gr,int originen,int destination ,int *err)
    {
     
    }
    est ce que je peux le faire avec l'algorithme de warshall ?

  2. #2
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    C'est normal que tu définisses les types Ville et Ligne avant que tes structures soient définies ?

    Ensuite, rédéfinir les types VilleOrig et VilleDest, est ce que c'est vraiment utile ?

    Pourquoi dans ta structure Tarete, il y a des pointeurs sur des arêtes ?
    Tu veux faire une liste chaînée ? Dans ce cas, il faudrait un type supplémentaire, car ça fait gros mélange là.

    Même remarque pour Tnoeud. De plus, tu définis:
    Ligne *listeAretes;
    Mais tu n'as aucun moyen de connaître le nombre d'arêtes !


    Et ta définition du type graphe, je n'ai pas l'impression qu'elle soit très classique, un graphe n'a pas d' noeud d'origine ou de destination, ce sont les chemins !
    Je ne répondrai à aucune question technique en privé

  3. #3
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    Pour savoir si un chemin existe entre deux sommets d'un graphe, il suffit de faire un parcourt en profondeur à partir du sommet A, si le sommet B est visité à un moment, on renvoit Vrai, et Faux sinon.
    Je ne répondrai à aucune question technique en privé

  4. #4
    Membre à l'essai
    Inscrit en
    Juillet 2006
    Messages
    18
    Détails du profil
    Informations forums :
    Inscription : Juillet 2006
    Messages : 18
    Points : 12
    Points
    12
    Par défaut
    svp si vous pouvez donner plus des explication sur parcourt en profondeur à partir du sommet A?

  5. #5
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    Déjà, de manière classique, un graphe est défini comme suit:

    G=(V,E) où V est un ensemble fini qu'on appelle des sommets (Vertex en anglais) et E est une partie de V² qu'on appelle les arêtes (Edge en anglais).

    Par exemple: G=({1,2,3},{(1,2),(1,3)}) est le graphe qui a les sommets 1,2 et 3 et les arêtes : (1,2) et (1,3).

    On dit qu'un sommet A est un successeur d'un sommet B dans le graphe G si l'arêtes (A,B) existe.

    Le parcourt en profondeur, on regarde récursivement les successeurs de chaques sommets.

    On définit un tableau couleur qui est de la taille du nombre de sommet. Le tableau prend classiquement trois valeurs:
    Noir : le sommet n'a pas été visité
    Blanc : le sommet a été visité
    Gris : le sommet est en cours de visite ou doit être visité

    L'algo s'écrit:

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    11
    12
    fonction visitersommet(u : sommet)
     
    couleur[u] = Gris
     
    Pour tout v successeur de u faire
     Si couleur[v] = blanc
      visitersommet(v)
    fin pour 
     
    couleur[u] = noir
     
    fin de la fonction

    Code : Sélectionner tout - Visualiser dans une fenêtre à part
    1
    2
    3
    4
    5
    6
    7
    8
    9
    10
    fonction existeChemin( A; B)
     
    initialisation du tableau : Le tableau couleur doit être blanc partout.
    visitersommet(A)
    Si couleur(B) = noir
      Retourner Vrai
    Sinon
     Retourn Faux
     
    finfonction
    Je ne répondrai à aucune question technique en privé

  6. #6
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    Il faut noter que tu peux aller plus vite et t'arrêter dès que le sommet de destination est en cours de visite.

    De plus, l'algorithme est récursif, et en langage C, cela peut être dangereux de garder la fonction récursive, il peut vite y avoir un dépassement de pile, donc je te conseille de transformer l'algorithme en non récursif, sinon, sur des gros graphes, ça peut vite planter !!
    Je ne répondrai à aucune question technique en privé

  7. #7
    Membre à l'essai
    Inscrit en
    Juillet 2006
    Messages
    18
    Détails du profil
    Informations forums :
    Inscription : Juillet 2006
    Messages : 18
    Points : 12
    Points
    12
    Par défaut
    merci de votre reponse
    JAZAKA LAHOU KHAYRAN
    merci pour tous

  8. #8
    Rédacteur

    Avatar de millie
    Profil pro
    Inscrit en
    Juin 2006
    Messages
    7 015
    Détails du profil
    Informations personnelles :
    Localisation : France

    Informations forums :
    Inscription : Juin 2006
    Messages : 7 015
    Points : 9 818
    Points
    9 818
    Par défaut
    Si tu t'interesses au graphes, tu peux avoir un bon cours sur:

    http://www.enseirb.fr/~lapoire/1ereAnnee/Graphes/Cours/
    Je ne répondrai à aucune question technique en privé

Discussions similaires

  1. question sur les 2-graphes
    Par yaris20 dans le forum Algorithmes et structures de données
    Réponses: 8
    Dernier message: 24/08/2008, 20h01
  2. question sur les vertex buffer et index buffer
    Par airseb dans le forum DirectX
    Réponses: 9
    Dernier message: 25/08/2003, 03h38
  3. question sur les variables globales et les thread posix
    Par souris_sonic dans le forum POSIX
    Réponses: 5
    Dernier message: 13/06/2003, 14h59
  4. Question sur les handles et les couleurs...
    Par MrDuChnok dans le forum C++Builder
    Réponses: 7
    Dernier message: 29/10/2002, 09h45
  5. question sur les message box !
    Par krown dans le forum Langage
    Réponses: 7
    Dernier message: 02/08/2002, 17h11

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