Besoin d'aide sur algorithme d'un graphe
Résolu
bonjour,
je suis novice en programmation en C++ et j'ai besoin d'aide pour un algorithme,je vous donne l'énoncé:
é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.
je c ke jen demande bocou tro mé je voudré savoir ou est ce ke je pourrai récupéré le logiciel de linux pour la programmation en C++ gratuitement.en espérant une réponse positive de votre et le plus rapidement je vous remercie d'avance.
je suis novice en programmation en C++ et j'ai besoin d'aide pour un algorithme,je vous donne l'énoncé:
é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.
je c ke jen demande bocou tro mé je voudré savoir ou est ce ke je pourrai récupéré le logiciel de linux pour la programmation en C++ gratuitement.en espérant une réponse positive de votre et le plus rapidement je vous remercie d'avance.
A voir également:
- Besoin d'aide sur algorithme d'un graphe
- Logiciel algorithme euromillion - Télécharger - Loisirs créatifs
- Logiciel algorithme gratuit - Télécharger - Édition & Programmation
- Algorithme euromillion excel gratuit - Forum Algorithmes / Méthodes
- Graphe easy - Télécharger - Études & Formations
- Algorithme ajout rapide snapchat - Forum Snapchat
14 réponses
tu veux installer quoi? l'algorithme? le C++? le programme correspondant a l'agorithme, que tu as ecris a la fac?
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)
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
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
...
//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|.
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
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
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
j ai besoin d un programme en c++ qui fais le parcours en profondeur dont un,e liste adjacence veillez m aide merci
