Pbleme langage C projet construction de graph
Résolu/Fermé
nawel
-
19 oct. 2001 à 10:15
mamiemando Messages postés 33077 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 18 avril 2024 - 14 janv. 2011 à 11:29
mamiemando Messages postés 33077 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 18 avril 2024 - 14 janv. 2011 à 11:29
A voir également:
- Pbleme langage C projet construction de graph
- Langage ascii - Guide
- Logiciel gratuit calcul de matériaux construction - Télécharger - Sciences & Techniques
- Gantt projet - Télécharger - Gestion de projets
- Simulateur de construction 14 - Télécharger - Simulation
- Yed graph editor - Télécharger - Photo & Graphisme
7 réponses
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
7 748
26 avril 2007 à 15:07
26 avril 2007 à 15:07
Bon ben pour commencer il faut définir une structure de sommet, d'arc, et de graphe. Idéalement il faudrait séparer la notion d'adjacence et l'information stockée dans un sommet (resp sommet). Nous on va faire simple on va utiliser une seule structure pour décrire entièrement un sommet (adjacence+données) et de même pour un arc, mais pour avoir un graphe vraiment générique il faudrait séparer ces deux notions. On va faire un graphe avec des sommets qui stocke un identifiant entier, et des arcs qui stockent un poids entier.
Pour commencer quelles fonctionnalités veux-tu dans ton graphe :
1- veux-tu pouvoir trouver les successeur d'un sommet et ses prédecesseurs, ou juste les successeurs suffisent (adjacence simple ou double) ?
2- est-ce que le graphe est suffisamment petit ou dense pour stocker des tableaux plutôt que des listes ? En particulier en dessous de quelques milliers de sommets tu peux passer par des tableaux sans problème et gagner en efficacité (en gros la complexité pour une recherche dans une liste serait O(n) alors qu'avec un arbre ce serait du O(log(n)) et un tableau du O(1))
3- est-ce que le graphe peut avoir des arcs parallèles (ie plusieurs arcs pour une paire de sommet donnée)
4- est-ce que le graphe est orienté ?
De toutes ces questions vont découler la structure de donnée utilisée pour décrire ton graphe.
Par ailleurs est ce que ton projet doit être codé en C pur ou as-tu le droit au C++ (qui nous permettrait de gagner beaucoup de temps pour coder ton implémentation de graphe). Pour information il faut savoir que tout ce qu'on va faire là a déjà été fait dans la lib boost (c++) mais là je suppose que c'est un exercice pédagogique.
Bonne chance
Pour commencer quelles fonctionnalités veux-tu dans ton graphe :
1- veux-tu pouvoir trouver les successeur d'un sommet et ses prédecesseurs, ou juste les successeurs suffisent (adjacence simple ou double) ?
2- est-ce que le graphe est suffisamment petit ou dense pour stocker des tableaux plutôt que des listes ? En particulier en dessous de quelques milliers de sommets tu peux passer par des tableaux sans problème et gagner en efficacité (en gros la complexité pour une recherche dans une liste serait O(n) alors qu'avec un arbre ce serait du O(log(n)) et un tableau du O(1))
3- est-ce que le graphe peut avoir des arcs parallèles (ie plusieurs arcs pour une paire de sommet donnée)
4- est-ce que le graphe est orienté ?
De toutes ces questions vont découler la structure de donnée utilisée pour décrire ton graphe.
Par ailleurs est ce que ton projet doit être codé en C pur ou as-tu le droit au C++ (qui nous permettrait de gagner beaucoup de temps pour coder ton implémentation de graphe). Pour information il faut savoir que tout ce qu'on va faire là a déjà été fait dans la lib boost (c++) mais là je suppose que c'est un exercice pédagogique.
Bonne chance
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
7 748
31 oct. 2007 à 13:36
31 oct. 2007 à 13:36
Merci de poser ton problème dans un nouveau sujet car ça n'a rien à voir avec le sujet de départ.
L'idée consiste simplement à maintenir une carte colorée (la couleur permet en particulier de savoir si un sommet est atteignable depuis la source ou non) de ton graphe pour voir les sommets ont déjà été visités. Tu peux t'inspirer de ça pour voir comment l'implémenter :
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/depth_first_search.html
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/breadth_first_search.html
Dans l'implémentation de la lib boost, ces 2 algorithmes sont codés de tel sortes qu'ils appellent des fonctions particulières en fonction de la situation (arc pas encore visité, sommet déjà visité, sommet pas encore visité etc...) au travers d'un "visiteur". Dans ton cas le visiteur ne ferait rien, l'objectif consiste juste à remplir la carte colorée. Si tu veux de plus amples précisions merci d'ouvrir un nouveau sujet dans le forum programmation.
Bonne chance
L'idée consiste simplement à maintenir une carte colorée (la couleur permet en particulier de savoir si un sommet est atteignable depuis la source ou non) de ton graphe pour voir les sommets ont déjà été visités. Tu peux t'inspirer de ça pour voir comment l'implémenter :
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/depth_first_search.html
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/breadth_first_search.html
Dans l'implémentation de la lib boost, ces 2 algorithmes sont codés de tel sortes qu'ils appellent des fonctions particulières en fonction de la situation (arc pas encore visité, sommet déjà visité, sommet pas encore visité etc...) au travers d'un "visiteur". Dans ton cas le visiteur ne ferait rien, l'objectif consiste juste à remplir la carte colorée. Si tu veux de plus amples précisions merci d'ouvrir un nouveau sujet dans le forum programmation.
Bonne chance
Bonjour,
je besoin de faire l'algorithme parcours en largeur et en profendeur et je ne sais pas comment le faire et comment commence
merci
ali
je besoin de faire l'algorithme parcours en largeur et en profendeur et je ne sais pas comment le faire et comment commence
merci
ali
hmm... il s'agit surement d'un sujet très intéressant
J'imagine qu'il s'agit d'un exercice pour mettre en pratique les structures, les pointeurs et les accès aux fichiers.
Mais si tu nous en disait plus, on pourrait sans doute t'aider.
Envoie moi ton sujet par mail si tu veux.
J'imagine qu'il s'agit d'un exercice pour mettre en pratique les structures, les pointeurs et les accès aux fichiers.
Mais si tu nous en disait plus, on pourrait sans doute t'aider.
Envoie moi ton sujet par mail si tu veux.
merci bcoup yaubi
je commence vraiment à desesperer, étant completement novice en programmation.
En fait, on nous a donne un algorithme permettant de creer un arc qu on doit implementer en c de 2 manieres differentes:allocation statique et dynamique
et voila ce qu on a commence à faire
une fonction creer_arc(d o:type_sommet,d e:type_sommet):type_ptr_arc
et ensuite on doit faire une procedure creer _graphe(d nom_fichier:type_chaine)
ou il faut qu on recupere les sommets des arcs dans un fichier.
et enfin il faut tout détruire arc et graphe.
et je peche surtout, le plus important bien sur, au niveau de la logique et comment utiliser les pointeurs pour remplir les cases et reactualiser.
je te remercie pour toute lumiere que tu m apporteras
merci
je commence vraiment à desesperer, étant completement novice en programmation.
En fait, on nous a donne un algorithme permettant de creer un arc qu on doit implementer en c de 2 manieres differentes:allocation statique et dynamique
et voila ce qu on a commence à faire
une fonction creer_arc(d o:type_sommet,d e:type_sommet):type_ptr_arc
et ensuite on doit faire une procedure creer _graphe(d nom_fichier:type_chaine)
ou il faut qu on recupere les sommets des arcs dans un fichier.
et enfin il faut tout détruire arc et graphe.
et je peche surtout, le plus important bien sur, au niveau de la logique et comment utiliser les pointeurs pour remplir les cases et reactualiser.
je te remercie pour toute lumiere que tu m apporteras
merci
Je ne comprends pas bien le but de tout ça.
Eclaircissons :
1
. tu possèdes une fonction qui créer un arc (de cercle ?)
. tu lui donnes en entrée les caractéristiques des deux sommets
. peux-tu détailler le type sommet ?
. en sortie, elle te renvoie un pointeur vers un arc
. peux-tu détailler le type ptr_arc
. mais concrètement, je ne vois pas trop ce qu'elle fait, que calcule-t-elle ? ou bien elle afiche quelque chose mais quel intéret de renvoyer un pointeur ? ou peut-être qu'elle dessine l'arc dans une matrice désignée par ce pointeur ?
. peux-tu détailler le rôle de cette fonction ?
2
. tu possèdes une seconde fonction qui est censée construire un graphe (ensemble d'arcs) à l'aide de la fonction précédente et en tirant ses informations de constructions d'un fichier
. peux-tu m'en dire plus sur le type de graphe ?
. peuc-tu me détailler le contenu de ton fichier ?
3. tu parles de C, es-tu bien sur qu'il s'agit de ce langage et non de C++ ?
Si tu as un sujet, tu peux aussi me l'envoyer. Toutes ces informations me sont nécessaires pour que je puisse t'aider. Il faut absoluement que je comprenne ce que tu dois faire, sinon je risquerais de te donner de fausses indications.
Yoann
Eclaircissons :
1
. tu possèdes une fonction qui créer un arc (de cercle ?)
. tu lui donnes en entrée les caractéristiques des deux sommets
. peux-tu détailler le type sommet ?
. en sortie, elle te renvoie un pointeur vers un arc
. peux-tu détailler le type ptr_arc
. mais concrètement, je ne vois pas trop ce qu'elle fait, que calcule-t-elle ? ou bien elle afiche quelque chose mais quel intéret de renvoyer un pointeur ? ou peut-être qu'elle dessine l'arc dans une matrice désignée par ce pointeur ?
. peux-tu détailler le rôle de cette fonction ?
2
. tu possèdes une seconde fonction qui est censée construire un graphe (ensemble d'arcs) à l'aide de la fonction précédente et en tirant ses informations de constructions d'un fichier
. peux-tu m'en dire plus sur le type de graphe ?
. peuc-tu me détailler le contenu de ton fichier ?
3. tu parles de C, es-tu bien sur qu'il s'agit de ce langage et non de C++ ?
Si tu as un sujet, tu peux aussi me l'envoyer. Toutes ces informations me sont nécessaires pour que je puisse t'aider. Il faut absoluement que je comprenne ce que tu dois faire, sinon je risquerais de te donner de fausses indications.
Yoann
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
Pour ceux qui souhaitent des sources en C de graphes:
http://www.arbredeslemuriens.com/Algorithmes.php?Algo=AlgoC
http://www.arbredeslemuriens.com/Algorithmes.php?Algo=AlgoC
