Visualizzazione dei risultati da 1 a 8 su 8
  1. #1
    Utente di HTML.it
    Registrato dal
    May 2012
    Messaggi
    213

    [C++] Consiglio rappresentazione di un grafo

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

  2. #2
    Utente di HTML.it L'avatar di shodan
    Registrato dal
    Jun 2001
    Messaggi
    2,381
    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.
    This code and information is provided "as is" without warranty of any kind, either expressed
    or implied, including but not limited to the implied warranties of merchantability and/or
    fitness for a particular purpose.

  3. #3
    Utente di HTML.it
    Registrato dal
    May 2012
    Messaggi
    213
    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

  4. #4
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,590
    Quote Originariamente inviata da shodan Visualizza il messaggio
    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)
    Ultima modifica di Scara95; 20-05-2018 a 02:59
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

  5. #5
    Utente di HTML.it L'avatar di shodan
    Registrato dal
    Jun 2001
    Messaggi
    2,381
    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).
    This code and information is provided "as is" without warranty of any kind, either expressed
    or implied, including but not limited to the implied warranties of merchantability and/or
    fitness for a particular purpose.

  6. #6
    Quote Originariamente inviata da shodan Visualizza il messaggio
    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).
    Amaro C++, il gusto pieno dell'undefined behavior.

  7. #7
    Utente di HTML.it L'avatar di shodan
    Registrato dal
    Jun 2001
    Messaggi
    2,381
    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().
    This code and information is provided "as is" without warranty of any kind, either expressed
    or implied, including but not limited to the implied warranties of merchantability and/or
    fitness for a particular purpose.

  8. #8
    Utente di HTML.it L'avatar di Scara95
    Registrato dal
    Jul 2009
    residenza
    Zimella (VR)
    Messaggi
    2,590
    Quote Originariamente inviata da shodan Visualizza il messaggio
    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.
    "Quid enim est, quod contra vim sine vi fieri possit?" - Cicerone, Ad Familiares

Permessi di invio

  • Non puoi inserire discussioni
  • Non puoi inserire repliche
  • Non puoi inserire allegati
  • Non puoi modificare i tuoi messaggi
  •  
Powered by vBulletin® Version 4.2.1
Copyright © 2024 vBulletin Solutions, Inc. All rights reserved.