Lista di adiacenza

In algebra computazionale, le liste di adiacenza sono una modalità di rappresentazione in memoria di grafi.

È probabilmente la rappresentazione più immediata a cui è possibile pensare e la più semplice da implementare, anche se in generale non la più efficiente in termini di spazio occupato.

L'idea della rappresentazione è semplicemente che ad ogni vertice $V$ viene associata una lista contenente tutti e soli i vertici $W$ tali che esista l'arco da $V$ a $W$ .

Supponendo di memorizzare tutte le coppie del tipo (n, L), dove L è la lista di adiacenza del vertice n-esimo, si ottiene una descrizione univoca del grafo. In alternativa, se si stabilisce di ordinare le liste di adiacenza, non è necessario memorizzare esplicitamente anche gli indici n dei vertici.

Efficienza[modifica | modifica wikitesto]

Supponendo di avere un grafo con n vertici ed m archi (orientati) che li uniscono, e supponendo di memorizzare le liste di adiacenza nell'ordine (in modo da non dovere memorizzare esplicitamente gli indici), avremo che ogni arco compare in una ed una sola lista di adiacenze, e vi compare in quanto numero del vertice a cui punta. Si deve quindi memorizzare un totale di m numeri minori o uguali di n, per un costo totale di

m\,\log _{2}n

Questo costo è in generale sub-ottimale (per m dell'ordine di n^2, diventa circa $n^{2}\log _{2}n$ , contro l' $n^{2}$ della rappresentazione mediante matrice di adiacenza). Tuttavia può essere un buon risultato se si deve memorizzare grafi sparsi (con m tipicamente dell'ordine di n).

Non esiste un modo ovvio di ottimizzare questa rappresentazione per grafi non orientati; ogni arco deve essere memorizzato nelle liste di adiacenza di entrambi i vertici che esso connette, dimezzando così l'efficienza. Lo stesso discorso vale se il grafo è orientato ma abbiamo bisogno di un metodo efficiente per conoscere gli archi entranti in un certo vertice; in questo caso è conveniente associare ad ogni vertice due liste: quella degli archi entranti e quella degli archi uscenti.

Per quel che riguarda l'efficienza in termini di tempo, la rappresentazione per liste di adiacenza si comporta piuttosto bene sia nell'accesso che nell'inserimento, effettuando le operazioni principali in tempo $O(n)$ .

Sparsità[modifica | modifica wikitesto]

È possibile vedere la rappresentazione per liste di adiacenza come una particolare rappresentazione sparsa della matrice di adiacenza, in cui ad ogni riga viene associata una lista contenente gli indici delle celle diverse da 0.