Quale struttura dati utilizzare per salvare l'indirizzo degli spigoli in profondità prima ricerca?

1

Attualmente sto cercando di scrivere la mia prima ricerca approfondita. Ho creato una classe chiamata nodo.

class node{ 
    private:
      bool is_visited;
      <data structure to collect edges>
    public : 
      size_t get_number_of_edges();
      void   set_is_visited( bool val);
      bool   get_is_visited();
};

Il nodo è fondamentalmente un vertice per DFS. Devo ancora creare un altro DFS di classe, che inserirà questo nodo nel suo membro privato (attraverserò quest'ultimo ponte). Questo nodo deve memorizzare l'indirizzo di altri nodi (bordi). Mi chiedevo quale struttura dati dovrei usare per salvare l'indirizzo dei bordi.

Stavo pensando di usare il vettore.

vector<node*> collect_edges;

o dovrei usare la lista?

list<node*> collect_edges;

Personalmente non vedo alcuna differenza.

    
posta solti 23.05.2016 - 06:23
fonte

1 risposta

2

Dovresti prendere in considerazione:

  • il tipo di grafico
  • le operazioni di cui hai bisogno

Per un semplice grafico, al contrario di una multigrafo , i bordi formano un set (ogni spigolo è una coppia non ordinata di vertici distinti) quindi potresti anche considerare std::set<node *> .

Un set è una buona scelta anche se devi mantenere un ordine tra i bordi.

              vector   list   set
removal        O(1)    O(1)   O(1)
enumeration    O(n)    O(n)   O(n)
insertion      O(1)    O(1)   O(log n)

compactness     *
cache friendly  *

Un elenco di margini basato su std::list non sembra la soluzione giusta. Soprattutto se hai intenzione di costruire il grafico ed eseguire più DFS.

Un riferimento interessante è Scelta di Edgelist e VertexList , ha molti dettagli ma la classe boost::adjacency_list è molto generica e alcune considerazioni non valgono per la tua classe.

    
risposta data 23.05.2016 - 12:00
fonte

Leggi altre domande sui tag