[C++] Consiglio rappresentazione di un grafo

[Eduadie]

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

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

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

#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);
};

[shodan]

Una lista è qualcosa a cui puoi togliere e aggiungere elementi a piacimento, il vector può fare la stessa cosa.
Le differenze tra i due sono:
lista -> ricerca in O(n), inserimento testa/in mezzo/ coda in O(1)
vector -> ricerca in O(1), inserimento in coda O(1), inserimento testa /in mezzo O(n) (se non ricordo male).
Quindi usare un vector al posto di una lista non è di per se sbagliato, ma dovresti considerare quali sono le operazioni più frequenti che fai.

In una mia implementazione, ad esempio, invece di una lista ho usato una mappa per le varie adiacenze usando una unordered_map.

[Eduadie]

Grazie per la risposta.
Era un po quella che mi aspettavo ovviamente.
La mia preoccupazione era una rappresentazione sbagliata del grafo in generale. Giustamente proprio perchè uso molta ricerca e inserimento in coda credo che il vector sia una soluzione migliore rispetto alla lista. Speriamo di aver considerato tutto nel modo giusto

[Scara95]

lista -> ricerca in O(n), inserimento testa/in mezzo/ coda in O(1)

Che l'insert sia O(1) è una mezza bugia perché prima devi ottenere un'iteratore alla posizione che è un'operazione (in generale) O(n)

edit: per quanto riguarda i vettori invece, l'inserimento in coda è O(1) amortizzato, non O(1)

[shodan]

https://baptiste-wicht.com/posts/201...r-vs-list.html
qui c'è una comparazione di list vs vector.

Che l'insert sia O(1) è una mezza bugia perché prima devi ottenere un'iteratore alla posizione che è un'operazione (in generale) O(n)

Ok, ma la ricerca dell'iteratore è O(n), l'inserimento in mezzo no, quello è O(1). Per testa/coda bastano due puntatori fissi a testa e coda per avere l'inserimento in O(1).

Non capito invece il discorso dell'O(1) amortizzato del vector, a me risulta che che sia O(1) nell'intervallo di esistenza (a meno che non ti riferisca a una possibile riallocazione interna).

[MItaly]

Non capito invece il discorso dell'O(1) amortizzato del vector, a me risulta che che sia O(1) nell'intervallo di esistenza (a meno che non ti riferisca a una possibile riallocazione interna).

In genere si parla di O(1) ammortizzato per la push_back di un vector perché è O(1) finché size() <= capacity(), mentre quando deve riallocare hai un O(n); il vector però ha una crescita della capacity esponenziale (ad ogni riallocazione si ha che capacity_nuova = k*capacity_vecchia, con k in genere attorno ad 1.5); la push_back "costosa" avviene una volta ogni k^n push_back, ergo si ha che in media una push_back è O(1 + n/k^n), che quindi è O(1) (l'esponenziale a denominatore uccide il termine lineare).

[shodan]

Ok, ma allora se spostiamo il discorso dalla teoria all'implementazione, faccio una stima euristica di elementi da inserire, effettuo una .reserve() un po' sovradimensionata prima di inserire elementi e quanto meno riduco il costo dell'ammortamento nel caso n < size().

[Scara95]

Ok, ma la ricerca dell'iteratore è O(n), l'inserimento in mezzo no, quello è O(1). Per testa/coda bastano due puntatori fissi a testa e coda per avere l'inserimento in O(1).

Non ho mica detto che è una bugia, ho detto che è una mezza bugia. Quando vai a cercare qualcosa in mezzo di rado capita di avere già un iteratore bello e posizionato così dal nulla. L'inserimento è O(1), quando hai già la posizione, che è un dettaglio che molti si perdono. Era solo una precisazione e un invito a stare in guardia.