Due domande sui grafi

#1

  1. come gestisco(ovvero come inizializzo, dichiaro e mando a video) array di vettori di pair?

  2. sunnydale: https://pastebin.com/TqG0Q3tY
    Come posso migliorarlo(40/100)?

#2

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 :smile:
Fabio.

#3

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?

#4

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

#5

Ti consiglio di leggere questo post :smiley:
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.