Implementazione di Grafi in c++

Linguaggi
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 Mi Piace