Programme de parcours en largeur BFS
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 :
Code:
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 graphe.cpp :
Code:
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.h :
Code:
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();
}; |
Fichier Sommet.cpp
Code:
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;
} |
Je n'arrive pas vraiment à appliquer l'algorithme de parcours en largeur que je pensais avoir bien compris, à l'organisation de mon programme.
Si l'un d'entre vous pourrait m'aider ça sera vraiment sympa, merci d'avance :)
