Besoin d'aide sur algorithme d'un graphe
Résolu/Fermé
sonia
-
10 mai 2005 à 17:34
mamiemando Messages postés 33077 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 18 avril 2024 - 2 mai 2009 à 14:09
mamiemando Messages postés 33077 Date d'inscription jeudi 12 mai 2005 Statut Modérateur Dernière intervention 18 avril 2024 - 2 mai 2009 à 14:09
A voir également:
- Besoin d'aide sur algorithme d'un graphe
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Ecrire un algorithme qui permet de resoudre ax²+bx+c=0 - Forum Programmation
- Tester un algorithme en ligne - Forum Programmation
- Graphe excel - Guide
- Algorithme maximum de 3 nombres ✓ - Forum Algorithmes / Méthodes
14 réponses
sam3000
Messages postés
1225
Date d'inscription
mercredi 22 décembre 2004
Statut
Membre
Dernière intervention
13 juin 2005
144
10 mai 2005 à 17:43
10 mai 2005 à 17:43
tu veux installer quoi? l'algorithme? le C++? le programme correspondant a l'agorithme, que tu as ecris a la fac?
kij_82
Messages postés
4088
Date d'inscription
jeudi 7 avril 2005
Statut
Contributeur
Dernière intervention
30 septembre 2013
857
10 mai 2005 à 17:37
10 mai 2005 à 17:37
euh.. tu as quel distri de linux ? Normalement le pas pour faire du C/C++ est déjà mis avec l'installation (encore faut-il l'avoir demandé lors de l'install)
sam3000
Messages postés
1225
Date d'inscription
mercredi 22 décembre 2004
Statut
Membre
Dernière intervention
13 juin 2005
144
10 mai 2005 à 17:38
10 mai 2005 à 17:38
tu veux du gratuit, tu as :
GNU C/C++ : http://gcc.gnu.org/
DEV-C++ : http://www.bloodshed.net
le premier est le language officiel C++ pour linux
sinon, tu peux toujours poser des questions précises (un algorithme complet, désolé mais je ne l'ai pas)
GNU C/C++ : http://gcc.gnu.org/
DEV-C++ : http://www.bloodshed.net
le premier est le language officiel C++ pour linux
sinon, tu peux toujours poser des questions précises (un algorithme complet, désolé mais je ne l'ai pas)
en fait c ke l'algo il é mis en place a la fac et je veux l'installer ché moi mé je c pas comment l'obtenir
Vous n’avez pas trouvé la réponse que vous recherchez ?
Posez votre question
je crois que c facile un tel algo mais tu fais quoi au juste?
en ce moment , je ne suis pas chez moi mais tu peux essayer avec la programmation des threads c facile.
hahaha y a pas mieux que la prog en philosophie pas de casse tête.
essaies: http://starprog.net créer par bobstar
pro de prog
en ce moment , je ne suis pas chez moi mais tu peux essayer avec la programmation des threads c facile.
hahaha y a pas mieux que la prog en philosophie pas de casse tête.
essaies: http://starprog.net créer par bobstar
pro de prog
ce ke je veux c pouvoir écrire cet algorithme et le traduire en c++ ensuite,mais le plus gran souci c de pouvoir écrir l'algorithme ,il é pe etr facile pour toi mé tré difficile pour moi.tu peux m'aider alors
sam3000
Messages postés
1225
Date d'inscription
mercredi 22 décembre 2004
Statut
Membre
Dernière intervention
13 juin 2005
144
10 mai 2005 à 17:58
10 mai 2005 à 17:58
as tu un énoncé du pb au moins (algorithme de graphe, pour moi c'est vague)
l'énoncé c ce ke g écri tout o début
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
7 749
12 mai 2005 à 11:36
12 mai 2005 à 11:36
Pour ceux qui veulent l'aider :
- Un graphe est un ensemble de sommet (V) et d'arc (E) : G=(V,E)
- Les arcs peuvent relient deux sommets et peuvent être orientés ou non
Première question donc : ton graphe est-il orienté ?
Un circuit est une suite de sommet (e1,...,en) avec e1 qui part d'un sommet v1 et en qui arrive sur ce sommet en.
Exemple :
- Les villes forment les sommets d'un graphe.
- Les routes qui les relient forment les arcs.
Un circuit pourrait être Paris->Tours, Tours->Nice,Nice->Paris.
Je sais pas si ton graphe est de grande taille ou pas, mais il y a plusieurs façons de l'implémenter :
1- Soit avec une matrice d'adjacence (1 dans la case (i,j) si vi vj sont reliés 0 sinon).
2- Soit avec la classe set (STL) qui te permet de former les ensembles V et E sans avoir à gérer les doublons.
La première méthode est meilleure si ton graphe est grand (plus rapide,...) mais un peu plus compliquée à mettre en place. Il faudra par exemple faire une classe de matrice creuse.
La seconde méthode est assez facile à mettre en place mais nécessite de jeter un coup d'oeil à la STL. Jete un oeil ici pour te faire une idée :
http://etna.int-evry.fr/COURS/C++/CoursEA/node39.html
http://c.developpez.com/faq/cpp/?page=STL
Pour ce qui est des classes :
- Une classe graphe
- Une classe d'arc + une classe de sommet pour la deuxième méthode, sinon une classe de matrice creuse.
Pour l'algo en lui même
* Méthode 1. Soit M la matrice d'adjacence. Si ma mémoire est bonne MxM te donne la matrice d'adjacence pour les sommets séparés de deux arcs, MxMxM pour trois arcs et ainsi de suite. Si tu as un terme à 1 sur la diagonale c'est donc que tu as détecté un circuit.
* Méthode 2 (plus simple !).
f(s){
Marquer les voisins de s (prévoir un attribut
- Un graphe est un ensemble de sommet (V) et d'arc (E) : G=(V,E)
- Les arcs peuvent relient deux sommets et peuvent être orientés ou non
Première question donc : ton graphe est-il orienté ?
Un circuit est une suite de sommet (e1,...,en) avec e1 qui part d'un sommet v1 et en qui arrive sur ce sommet en.
Exemple :
- Les villes forment les sommets d'un graphe.
- Les routes qui les relient forment les arcs.
Un circuit pourrait être Paris->Tours, Tours->Nice,Nice->Paris.
Je sais pas si ton graphe est de grande taille ou pas, mais il y a plusieurs façons de l'implémenter :
1- Soit avec une matrice d'adjacence (1 dans la case (i,j) si vi vj sont reliés 0 sinon).
2- Soit avec la classe set (STL) qui te permet de former les ensembles V et E sans avoir à gérer les doublons.
La première méthode est meilleure si ton graphe est grand (plus rapide,...) mais un peu plus compliquée à mettre en place. Il faudra par exemple faire une classe de matrice creuse.
La seconde méthode est assez facile à mettre en place mais nécessite de jeter un coup d'oeil à la STL. Jete un oeil ici pour te faire une idée :
http://etna.int-evry.fr/COURS/C++/CoursEA/node39.html
http://c.developpez.com/faq/cpp/?page=STL
Pour ce qui est des classes :
- Une classe graphe
- Une classe d'arc + une classe de sommet pour la deuxième méthode, sinon une classe de matrice creuse.
Pour l'algo en lui même
* Méthode 1. Soit M la matrice d'adjacence. Si ma mémoire est bonne MxM te donne la matrice d'adjacence pour les sommets séparés de deux arcs, MxMxM pour trois arcs et ainsi de suite. Si tu as un terme à 1 sur la diagonale c'est donc que tu as détecté un circuit.
* Méthode 2 (plus simple !).
f(s){
Marquer les voisins de s (prévoir un attribut
WEMERICA
Messages postés
9
Date d'inscription
dimanche 22 mars 2009
Statut
Membre
Dernière intervention
16 avril 2013
>
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
8 avril 2009 à 15:51
8 avril 2009 à 15:51
bonjours j ai lu votre explication pour faire un algorithme d un graph je suis interesser par la premiere methode
de la matrice mais j ai pas compri ce que une matrice adjacente et comment faire une merci d avance
de la matrice mais j ai pas compri ce que une matrice adjacente et comment faire une merci d avance
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
7 749
12 mai 2005 à 14:35
12 mai 2005 à 14:35
...
//prévoir un attribut marque dans la classe sommet
si un de ces sommets était déjà marqué -> fin (circuit detecté)
sinon appeler f sur les voisins qui vienne d'être marqués.
}
Fin pour
Si ton graphe est connexe et que tu sors de la boucle pour alors c'est qu'il n'y a pas de circuit.
NB : Pour la version avec des matrices, tu peux t'arrêter au bout de |V| (card(V)) itérations car un circuit fait au maximum une longueur de |V|.
//prévoir un attribut marque dans la classe sommet
si un de ces sommets était déjà marqué -> fin (circuit detecté)
sinon appeler f sur les voisins qui vienne d'être marqués.
}
Fin pour
Si ton graphe est connexe et que tu sors de la boucle pour alors c'est qu'il n'y a pas de circuit.
NB : Pour la version avec des matrices, tu peux t'arrêter au bout de |V| (card(V)) itérations car un circuit fait au maximum une longueur de |V|.
sam3000
Messages postés
1225
Date d'inscription
mercredi 22 décembre 2004
Statut
Membre
Dernière intervention
13 juin 2005
144
10 mai 2005 à 18:25
10 mai 2005 à 18:25
enoncé: "écrire un algorithme pour savoir si un graphe est avec ou sans cicruit et si ce n'est pas le cas le découper par niveaux"
c'est tout? qu'est ce qu'un graphe exactement? à quoi ça sert? qu'est ce qu'un circuit?
c'est tout? qu'est ce qu'un graphe exactement? à quoi ça sert? qu'est ce qu'un circuit?
salut svp aide moi pour "ecrire un programme en c++ d'un graphe (les sommets,les arcs,...) svp aide moi je l'ai besoin dans 09 jours " merci bien
diegolo
Messages postés
13
Date d'inscription
jeudi 20 décembre 2007
Statut
Membre
Dernière intervention
2 avril 2008
1
24 déc. 2007 à 14:24
24 déc. 2007 à 14:24
salut nadia;
tu as trouver la solution ou pas.
et plus t ues d'ou??
tu as trouver la solution ou pas.
et plus t ues d'ou??
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
7 749
3 déc. 2007 à 20:53
3 déc. 2007 à 20:53
Si tu dois utiliser des graphes en C++ tu peux utiliser la librairie boost, qui propose une implémentation générique de graphe écrite en C++.
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/index.html
Si tu dois réimplémenter une classe de graphe, je te suggère d'ouvrir un nouveau post dans le forum programmation car c'est un problème différent de celui posé initialement. Dans une premier jet je t'invite à te familiariser avec la STL (standard template library) car tu vas en avoir besoin (notamment tout ce qui concerne les vector ou les map). Tout dépend de la manière dont tu implémentes ton graphe ceci dit...
Bonne chance
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/index.html
Si tu dois réimplémenter une classe de graphe, je te suggère d'ouvrir un nouveau post dans le forum programmation car c'est un problème différent de celui posé initialement. Dans une premier jet je t'invite à te familiariser avec la STL (standard template library) car tu vas en avoir besoin (notamment tout ce qui concerne les vector ou les map). Tout dépend de la manière dont tu implémentes ton graphe ceci dit...
Bonne chance
diegolo
Messages postés
13
Date d'inscription
jeudi 20 décembre 2007
Statut
Membre
Dernière intervention
2 avril 2008
1
24 déc. 2007 à 14:26
24 déc. 2007 à 14:26
salut;
je crois que tu as de grande connaissance dans ce domaine tu peux nous eclairer un peut si tu veut
merci et bonne fete.
je crois que tu as de grande connaissance dans ce domaine tu peux nous eclairer un peut si tu veut
merci et bonne fete.
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
7 749
30 déc. 2007 à 19:18
30 déc. 2007 à 19:18
Je ne peux pas t'expliquer toute la lib boost comme ça en un post :-) Dis-moi quels points t'intéresse et je vais essayer de t'éclairer.
0- En gros le concept : boost propose différentes implémentation de graphe générique. La manière dont est stocké la structure de graphe impacte directement sur son efficacité et sa taille en mémoire.
https://matthieu-brucher.developpez.com/tutoriels/cpp/boost/graph/implementation/
1- chaque sommet et chaque arc boost encapsule une structure appelé bundle. Par exemple si un graphe boost stocke un std::string (le nom du sommet) c'est la structure "vertex_bundled" qui va stocker cette information. Idem pour les arcs, si tu dois stocker un poids (par exemple sous forme d'int) c'est le edge_bundled qui va stocker ça.
2- on appelle descriptor un identifiant (pour les sommets vertex_descriptor, pour les arcs edge_descriptor). Vois-ca comme un entier pour l'identifiant de sommet et une paire d'entier pour l'identifiant d'arc.
3- de même que la STL propose des iterator, des reverse_iterator, des const_iterator, et des const_reverse_iterator, boost propose aussi une série d'itérator. Dans la STL, les iterators permettent de parcourir une structure complexes (par exemple un arbre rouge noir dans le cas des std::set). Dans boost c'est la même chose tu as des iterators spécifiques à ton graphe :
* les vertex_iterator : parcourent les sommets du graphes
* les edge_iterator : parcourent les arcs du graphe
* les out_edge_iterator : parcourent les arcs sortants d'un sommet
* les in_edges_iterator : parcourent les arcs entrant d'un sommet (pas toujours disponible selon la structure du graphe).
La combinaison de 0 et 1 permet de décrire une structure générique de graphe. 2 et 3 permettent de manipuler cette structure aisément.
4- Parfois boost utilise des traits. Ce sont des structures templates qui n'encapsulent que des typedef (pas d'information stockée, pas de méthode). Ca permet ainsi de récupérer facilement des types dépendant de paramtres template.
5- Une fois ta structure de graphe définie, boost propose toute une série d'algorithme (cf doc) s'appliquant à ta structure de graphe. L'avantage de boost c'est que c'est générique, très efficace, et plutôt bien fait même si parfois la doc est un peu "complexe" à appréhender.
6- boost propose aussi des visitor. Les visitors sont des structures passées en paramètre d'un algorithme (par exemple un depth first search) en vue de déclencher des fonctions à certains points clés de l'algorithme. Il est ainsi très facile de recoder son propre algorithme de marquage.
Cet aperçu ne traite que d'une partie de la lib boost (la BGL, boost graph library). Il y a encore bien d'autres choses, comme par exemple les serialization. SI ça t'intéresse je t'invite à jeter un oeil à la doc :
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/
Bonne chance
0- En gros le concept : boost propose différentes implémentation de graphe générique. La manière dont est stocké la structure de graphe impacte directement sur son efficacité et sa taille en mémoire.
https://matthieu-brucher.developpez.com/tutoriels/cpp/boost/graph/implementation/
1- chaque sommet et chaque arc boost encapsule une structure appelé bundle. Par exemple si un graphe boost stocke un std::string (le nom du sommet) c'est la structure "vertex_bundled" qui va stocker cette information. Idem pour les arcs, si tu dois stocker un poids (par exemple sous forme d'int) c'est le edge_bundled qui va stocker ça.
2- on appelle descriptor un identifiant (pour les sommets vertex_descriptor, pour les arcs edge_descriptor). Vois-ca comme un entier pour l'identifiant de sommet et une paire d'entier pour l'identifiant d'arc.
3- de même que la STL propose des iterator, des reverse_iterator, des const_iterator, et des const_reverse_iterator, boost propose aussi une série d'itérator. Dans la STL, les iterators permettent de parcourir une structure complexes (par exemple un arbre rouge noir dans le cas des std::set). Dans boost c'est la même chose tu as des iterators spécifiques à ton graphe :
* les vertex_iterator : parcourent les sommets du graphes
* les edge_iterator : parcourent les arcs du graphe
* les out_edge_iterator : parcourent les arcs sortants d'un sommet
* les in_edges_iterator : parcourent les arcs entrant d'un sommet (pas toujours disponible selon la structure du graphe).
La combinaison de 0 et 1 permet de décrire une structure générique de graphe. 2 et 3 permettent de manipuler cette structure aisément.
4- Parfois boost utilise des traits. Ce sont des structures templates qui n'encapsulent que des typedef (pas d'information stockée, pas de méthode). Ca permet ainsi de récupérer facilement des types dépendant de paramtres template.
5- Une fois ta structure de graphe définie, boost propose toute une série d'algorithme (cf doc) s'appliquant à ta structure de graphe. L'avantage de boost c'est que c'est générique, très efficace, et plutôt bien fait même si parfois la doc est un peu "complexe" à appréhender.
6- boost propose aussi des visitor. Les visitors sont des structures passées en paramètre d'un algorithme (par exemple un depth first search) en vue de déclencher des fonctions à certains points clés de l'algorithme. Il est ainsi très facile de recoder son propre algorithme de marquage.
Cet aperçu ne traite que d'une partie de la lib boost (la BGL, boost graph library). Il y a encore bien d'autres choses, comme par exemple les serialization. SI ça t'intéresse je t'invite à jeter un oeil à la doc :
https://www.boost.org/doc/libs/1_72_0/libs/graph/doc/
Bonne chance
firebrand
Messages postés
1
Date d'inscription
lundi 26 mai 2008
Statut
Membre
Dernière intervention
1 mai 2009
1 mai 2009 à 20:18
1 mai 2009 à 20:18
j ai besoin d un programme en c++ qui fais le parcours en profondeur dont un,e liste adjacence veillez m aide merci
mamiemando
Messages postés
33077
Date d'inscription
jeudi 12 mai 2005
Statut
Modérateur
Dernière intervention
18 avril 2024
7 749
2 mai 2009 à 14:09
2 mai 2009 à 14:09
