Implementazione di Grafi in c++


#1

Qualcuno potrbbe spiegarmi cosa sono e come implementare i grafi, la vista in ampiezza, quella in profondita e l’algoritomo di dijkstra?, quali esercizi base posso fare per prenderci la mano ad implementarli e usarli?(al di fuori di quelli presenti dal sito che essendo un po’ piu complessi, li proveri ha risolvere in un secondo momento nel quale avro’ più confindenza con le basi)
(ho gia letto delle guide al riguardo ma non le ho esatamente carpite).


#2

I grafi puoi considerarli come una struttura dati che contiene relazioni.
I soggetti delle relaizoni vengono chiamati nodi mentre la relazione che gli collega archi.
Per segnare queste relazioni si hanno due modi : la lista di adiacenza o la matrice.
Le liste di adiacenza vengono rappresentate tramite una struttura che ha la capacità di allocare dinamicamente la memoria come std::list o std::vector.
Mentre la matrice è la classica matrice dove utilizziamo la corrispondenza riga e colonna per segnare il collegamento tra due nodi.
Ogni rappresentazione ha i suoi vantaggi, quella della matrice di sapere in O(1) se due nodi sono collegati mentre la rappresentazione con la lista dobbiamo scorrere le adiacenze di uno dei due nodi e verificare che sia presente l’ altro.
Il vantaggio della lista di adiacenza è il ridotto utilizzo di memoria e la capacità di sapere quali nodi sono collegati senza controllare ogni ogni nodo presente nel grafo.
Le relazioni nei grafi possono essere bidireizonali o meno.
Se sono bidirezionali il collegamento collega sia A a B che B a A.
Se non lo sono può essere che A colleghi B ma non che B colleghi A.
Per capire al meglio perché i collegamenti non sono sempre bidirezionali prova a immaginare questa situazione: stanno dei ragazzi a cui piacciono delle ragazze ma il loro amore non viene ricambiato.
Ci possono essere casi in cui una relazione punti a se stessa.
Ecco il codice per la rappresentazione di una lista di adiacenza :

#define MAXN 1001
vector <int> adj[MAXN];

int main(){
	int archi;
	cin >> archi;
	for(int i = 0,a,b; i < archi; i++){
		cin >> a >> b;
		adj[a].push_back(b);
		// se i collegamenti sono bidirezionali
		adj[b].push_back(a);
	}
}

Mentre i due classici algoritmi per la visita dei grafi sono la dfs e la bfs.
La prima è una ricerca in profondità mentre la seconda in ampiezza.
DFS:

#define MAXN 1001
vector <int> adj[MAXN];
bool visti[MAXN];

void dfs(int nodo){
	visti[nodo] = true;
	for(int i = 0; i < adj[nodo].size();i++){
		int next = adj[nodo][i];
		if(visti[next])continue;
		dfs(next);
	}	
}

BFS:

#define MAXN 1001
vector <int> adj[MAXN];
bool visti[MAXN];

void bfs(int nodo){
	visti[nodo] = true;
	queue <int> q;
	q.push(nodo);
	while(!q.empty()){
		int nodo = q.front();
		q.pop();
		for(int i = 0; i < adj[nodo].size(); i++){
			int next = adj[nodo][i];
			if(visti[next])continue;
                        visti[next] = true;
			q.push(next);
		}
	}	
}

Qualche es facile : licenziamenti, ponti e isole, super marco 2, water park, curling e il classico dijkstra.
L’ algoritmo di dijkstra serve per risolvere il problema del percorso più breve tra due nodi.
L’ implementazione la puoi cercare o puoi provare a scriverla da solo.
Per salvarti il peso delle relazioni nella matrice puoi mettere direttamente il peso mentre nella lista ti salvi una coppia di valori.


#3

Grazie mille, in che senzo copia di valori?, provero a farli e ti farò sapere.


#4

Una coppia: in adj[x] hai i nodi collegati direttamente con x, se gli archi sono, come spesso accade, pesati allora ti interessa sapere sia quale è la destinazione dell’arco che parte da x ma anche la sua distanza.

Per memorizzare 2 informazioni in un’unica cella puoi:
1 crearti una struct.
2 Utilizzare i pair che risultano molto comodi.


#5

Cosa sono i pair?:sweat_smile:
la struct sarebbe del genere:

typedef struct arco{
    int nodo;
    int distanza;
}arc;
arc x;
cin>>x.nodo;
cin>>x.distanza;
adj[a].push_back(x);

#6

Il pair è una struct formata da due elementi, puoi scegliere il tipo di dato che vuoi per ogni elemento perfino mettere un altro pair.

#define MAXN 1001
    vector < pair <int,int> > adj[MAXN];

    int main(){
    	int archi;
    	cin >> archi;
    	for(int i = 0,a,b,w; i < archi; i++){
    		cin >> a >> b >> w;
    		adj[a].push_back(make_pair(b,w));
    		adj[b].push_back(make_pair(a,w));
    	}
    	// esempio di un pair contente un altro pair
    	pair < pair <int,int>, int> tmp;
         // modifico il primo elemento del primo 
            tmp.first.first = 3
         // modifico il secondo 
            tmp.second = 5
    }

La struct che hai fatto va benissimo.


#7

come si fa mettere quel tipo di formatazione quando ce del codice?


#8

è se dovessi richiamare quei valori?
è qualcosa del genere:
adj[nodo].first oppure adj[nodo].second
scusami se ti assillo di domande :sweat_smile:


#9

Si è così, comunque, l’argomento dei grafi è molto vasto, ti cito questo PDF per le territoriali http://www.imparando.net/sito/olimpiadi_di_informatica/guida_quinta_edizione.pdf

È difficile parlare in modo esaustivo (per il livello territoriali) di grafi, e lo è anche parlare della stl, figuriamoci entrambi!


#10

Copia e incolla il codice, lo evidenzi e premi sul tasto “Testo preformattato” oppure metti " ``` " prima e dopo il codice.