Vorrei chiedere un parere riguardo la rappresentazione di un grafo.
A breve dovrò affrontare l'esame di Algoritmi e strutture dati ed in uno dei due progetti mi è stato richiesto di implementare l'algoritmo Bellman-Ford. Il mio quesito adesso non riguarda nessun problema siccome credo di esserlo riuscito ad implementare correttamente, ma volevo chiedere un parere/suggerimento sul modo di implementare il grafo.
Un grafo viene rappresentato tramite o lista o matrice di adiacenza. Il fatto è che a me è venuto molto più facile rappresentarlo tramite due vector: uno contenente gli oggetti vertici e l'altro contente gli oggetti arco. E' sbagliato utilizzare questo e non uno dei due metodi citati prima o può andare comunque bene e cambia ovviamente solo dal punto di vista computazionale?
Per rendere l'idea vi posto le classi che ho utilizzato per darvi un'idea:
classe nodo
codice:
class nodo {
private:
string nomeVertice;
int peso;
int predecessore;
public:
nodo() {};
nodo(string n) {setNomeVertice(n);};
nodo(string n, int p, int pd) {setNomeVertice(n); setPeso(p); setPredecessore(pd);};
~nodo() {};
void setNomeVertice (string n) {nomeVertice = n;};
string getNomeVertice () {return nomeVertice;};
void setPeso (int p) {peso = p;};
int getPeso () {return peso;};
void setPredecessore (int p) {predecessore = p;};
int getPredecessore() {return predecessore;};
};
classe arco
codice:
class arco { private:
int partenza;
int destinazione;
int peso;
public:
arco () {};
arco (int p, int d, int w) {setPartenza(p); setDestinazione(d); setPeso(w);};
~arco () {};
void setPartenza (int p) {partenza = p;};
int getPartenza () {return partenza;};
void setDestinazione(int d) {destinazione = d;};
int getDestinazione() {return destinazione;};
void setPeso (int p) {peso = p;};
int getPeso () {return peso;};
};
classe bellmanford
codice:
#include "nodo.h"
#include "arco.h"
class bellmanford {
private:
vector<nodo> vertici;
vector<arco> archi;
void aggiungiVertice(nodo n) {vertici.push_back(n);};
void aggiungiArco (arco a) {archi.push_back(a);};
vector <nodo> getVertici () {return vertici;};
vector <arco> getArchi () {return archi;};
void showVertici ();
void showArchi();
nodo getSingoloVertice (int i) {return vertici[i];};
void sostituisciVertice (nodo n, int i) {vertici[i] = n;};
void inizializzaSingolaFonte ();
void stampaPercorsi (int i);
void rilassamento();
bool controlloCicli();
void inputCasoReale ();
void inputConsole ();
void inputFile();
int traduttoreNomeIndice(string nome);
int creaNumero (string nome);
public:
bellmanford () {};
~bellmanford() {};
void iniziaBellmanFord (int scelta);
};