Lista di Adiacenza¶

Un modo più efficiente di implementare un grafo sparso è l’uso di una lista di adiacenza. In una lista di adiacenza, abbiamo un oggetto per ogni vertice nell’oggetto Grafo. Ogni oggetto vertice nel grafo mantiene una lista dei vertici a cui esso è connesso. Nella nostra implementazione della classe Vertex useremo un dizionario piuttosto che una lista dove le chiavi del dizionario sono i vertici e i valori sono i pesi. Figura 3 mostra le liste di adiacenza del grafo in Figura 1.

Figura 3: Lista di adiacenza del grafo in Figura 1.

Il vantaggio della lista di adiacenza è che permette di rappresentare in modo compatto un grafo sparso. La lista di adiacenza permette anche di trovare facilmente tutti i collegamenti che sono direttamente connessi a un particolare vertice.