# Implementazione di Grafi in c++

**URL:** <https://forum.olinfo.it/t/implementazione-di-grafi-in-c/5424>\
**Category:** Linguaggi\
**Created:** [21 Novembre 2018, 8:30pm UTC](https://forum.olinfo.it/t/implementazione-di-grafi-in-c/5424 "2018-11-21T20:30:21Z")\
**Posts on this page:** 1\
**Showing post:** 2

<div class="post-metadata">

**Author:** ![zJack1342](https://forum.olinfo.it/user_avatar/forum.olinfo.it/zjack1342/32/711_2.png) [@zJack1342](https://forum.olinfo.it/u/zJack1342)\
**Post date:** [21 Novembre 2018, 9:02pm UTC](https://forum.olinfo.it/t/implementazione-di-grafi-in-c/5424/2 "2018-11-21T21:02:57Z")

</div>

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](http://www.cplusplus.com/reference/list/list/) o [std::vector](http://www.cplusplus.com/reference/vector/vector/?kw=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 :

```auto
#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:

```auto
#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:

```auto
#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](https://training.olinfo.it/#/task/licenziamenti/statement), [ponti e isole](https://training.olinfo.it/#/task/ois_ponti/statement), [super marco 2](https://training.olinfo.it/#/task/ois_monete/statement), [water park](https://training.olinfo.it/#/task/ois_waterslide/statement), [curling](https://training.olinfo.it/#/task/curling/statement) e il classico [dijkstra](https://training.olinfo.it/#/task/dijkstra/statement).  
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.

---

_[View the full topic](https://forum.olinfo.it/t/implementazione-di-grafi-in-c/5424)._