Bonjour,
dans le cadre de mon apprentissage du C++, j'aimerai réaliser un parcours en largeur (BFS) de tous les sommets de mon graphe (chargé depuis un fichier).
Cependant après plusieurs recherches sur le sujet, je n'arrive pas vraiment à l'appliquer à mes classes Sommets et Graphe suivantes :
Fichier graphe.h :
Fichier graphe.cpp :
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 #include "sommet.h" #include <iostream> #include <iomanip> #include <fstream> #include <string> #include <vector> #include <algorithm> #include <list> #include <cmath> #include <string> #include <stdexcept> class Graphe { private: int m_orient, m_ordre, m_taille; std::vector<Sommet*> m_sommets; std::vector<unsigned char> visite; public: void Afficher() const; Graphe(std::string nomFichier); void BFS(int choix); };
Fichier Sommet.h :
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 #include "graphe.h" Graphe::Graphe(std::string nomFichier) { std::ifstream ifs{ nomFichier }; int orient; ifs >> m_orient; int ordre; //lecture de l'ordre ifs >> m_ordre; int taille; ifs >> m_taille; for (int i = 0; i < 15; ++i) m_sommets.push_back(new Sommet{ i }); int id1, id2; for (int i = 0; i <= 16; ++i) { ifs >> id1 >> id2; m_sommets[id1]->adja(id2); m_sommets[id2]->adja(id1); } } void Graphe::Afficher() const { std::cout << "orientation : " << m_orient << " / ordre : " << m_ordre << " / taille : " << m_taille << std::endl; std::cout << "Liste d'adjacence" << std::endl; for (size_t i = 0; i < m_sommets.size(); ++i) { std::cout << "Sommet nb " << m_sommets[i]->getNb() << " : "; m_sommets[i]->getAdja(); std::cout << std::endl; } }
Fichier Sommet.cpp
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 #include <iostream> #include <iomanip> #include <istream> #include <fstream> #include <string> #include <vector> #include <list> #include <algorithm> #include <cmath> #include <string> #include <stdexcept> class Sommet { private: int m_nb; std::vector<Sommet> m_adjacents; public: Sommet(std::istream& is); Sommet(int nb); int getNb(); void setNb(int nb); void adja(int nb); std::vector<Sommet> getAdja(); };
Je n'arrive pas vraiment à appliquer l'algorithme de parcours en largeur que je pensais avoir bien compris, à l'organisation de mon programme.
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 #include "sommet.h" Sommet::Sommet(std::istream& is) { is >> m_nb; if (is.fail()) throw std::runtime_error("Probleme lecture id,x,y d'une station"); } Sommet::Sommet(int nb) { m_nb = nb; } int Sommet::getNb() { return this->m_nb; } void Sommet::setNb(int nb) { m_nb = nb; } void Sommet::adja(int nb) { m_adjacents.push_back(nb); } std::vector<Sommet> Sommet::getAdja() { for (size_t i = 0; i < m_adjacents.size(); ++i) std::cout << m_adjacents[i].m_nb << " "; return m_adjacents; }
Si l'un d'entre vous pourrait m'aider ça sera vraiment sympa, merci d'avance
Partager