Che cos'è un grafo?

Un grafo è una struttura dati che modella un insieme di elementi e le connessioni tra di essi. Gli elementi sono chiamati vertici (o nodi) e le connessioni sono chiamate archi.

I grafi sono ovunque. I social network sono grafi (le persone sono vertici, le amicizie sono archi). Le mappe stradali sono grafi (gli incroci sono vertici, le strade sono archi). Internet, gli alberi delle dipendenze e le mappe dei giochi sono tutti grafi.

In questo corso ci concentriamo su un grafo non orientato: se un arco collega u e v, allora anche v è collegato a u. Non c'è una direzione. Useremo numeri interi come chiavi dei vertici, per mantenere le cose semplici.

Internamente memorizzeremo il grafo come una lista di adiacenza: una mappa da ogni vertice alla lista dei suoi vicini. In questo modo, per cercare i vicini di un vertice basta un singolo accesso alla mappa, che è ciò di cui hanno bisogno la maggior parte degli algoritmi sui grafi.

Le operazioni che implementeremo nella nostra classe Graph sono:

1. addVertex: Aggiungi un nuovo vertice senza archi.
2. addEdge: Collega due vertici.
3. hasEdge: Verifica se due vertici sono collegati.
4. getNeighbors: Ottieni la lista dei vicini di un vertice.
5. removeEdge: Scollega due vertici.
6. size: Conta quanti vertici ha il grafo.

Costruiamo una classe Graph!