-
come gestisco(ovvero come inizializzo, dichiaro e mando a video) array di vettori di pair?
-
sunnydale: https://pastebin.com/TqG0Q3tY
Come posso migliorarlo(40/100)?
Per il punto 1:
Il codice che uso viene interpretato in questo modo, ogni nodo ha un proprio vettore di pair che contiene gli archi che escono da quel nodo, il primo valore dell’arco è la destinazione mentre il secondo la distanza(ovviamente i parametri non sono tassativi ma sono un esempio).
Supponendo che tu voglia avere un vector di pair per ogni nodo allora il modo più semplice è questo:
// MAXN=numero massimo di nodi
const int MAXN=10000;
vector < pair < int , int > > adj[MAXN];
I tipi int ovviamente sono scambiabili con quelli che ti servono.
In questo modo in adj[x]
hai tutti gli archi uscenti dal nodo x.
Per inserire un nuovo arco uscente dal nodo x, diretto al nodo y e con distanza d allora dovrai fare:
// I due codici sono equivalenti
adj[x].push_back(make_pair(y,d));
adj[x].push_back({y,d});
Per scorrere gli archi uscenti dal nodo x devi fare:
for(int i=0;i<(int)adj[x].size();i++)
{
//adj[x][i] ora è un pair < int , int >
//Puoi accedere direttamente
int to=adj[x][i].first, dist=adj[x][i].second;
cout<<"To: "<<to<<" Dist: "<<dist<<"\n";
//Oppure copiare in un nuovo pair e utilizzare quello
pair < int , int > next=adj[x][i];
}
Per scorrerli puoi anche evitare di richiamare il metodo size() su ogni vector e fare:
for(auto current:adj[x])
{
//Do your stuff here
}
In questo caso current è un pair che assume all’iesima “passata” l’iesimo arco.
Per stampare tutto il grafo puoi fare:
//n=numero di nodi e grafo 0 based
for(int i=0;i<n;i++)
{
cout<<"Node: "<<i<<"\n";
for(auto current:adj[i])
cout<<"To: "<<current.first<<" Dist: "<<current.second<<"\n";
}
Se hai altri dubbi chiedi pure
Fabio.
Mentre per quanto riguarda il punto 2:
Il primo consiglio è proprio quello di utilizzare i vettori come spiegato sopra, in questo modo risolvi già i problemi di memoria.
L’idea di capire quando si forma il ciclo è la strada esatta, a questo punto traduci il codice e guarda se riesci ad evitare errori essendo più facile da gestire.
Una volta risolto con i vettori ti consiglio:
Una considerazione che puoi fare che ti permette di evitare i vettori è: sapendo che partendo da ogni nodo l’arco con luminosità minima è sempre lo stesso ha veramente senso memorizzare anche gli altri?
Sì, so che per questa caratteristica potrei anche evitare i grafi in questo esercizio ma il fatto è che vorrei imparare ad usarli e ad implementarli
Ti consiglio di leggere questo post
Per il ciclo che visita ogni adiacenza (for each) devi usare c++11 se non ricordo male con il comando -std=c++11.
Sul mio compilatore è neccessario.
Oltre al comodo auto per i for each puoi indicare direttamente il tipo di dato da usare, e se vuoi modificare l’ elemento a cui fai riferimento puoi accompagnarlo con la ‘&’.
for(pair <int,int> i : adj[nodo]){
// isturzioni bla bla istruzioni
// non modifica l' elemeto nel vettore
i.first = 5;
}
for(pair <int,int> &i : adj[nodo]){
// isturzioni
// modifica l' elemento nel vettore
i.first = 5;
}
Non ho provato se con auto funziona lo stesso, ma è sempre meglio specificare il tipo di dato.