Топ-100
Indietro

ⓘ Lista di adiacenza. In algebra computazionale, le liste di adiacenza sono una modalità di rappresentazione in memoria di grafi. È probabilmente la rappresentazi ..




Lista di adiacenza
                                     

ⓘ 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.

Lidea della rappresentazione è semplicemente che ad ogni vertice V {\displaystyle V} viene associata una lista contenente tutti e soli i vertici W {\displaystyle W} tali che esista larco da V {\displaystyle V} a W {\displaystyle 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.

                                     

1. Efficienza

Supponendo di avere un grafo con n vertici ed m archi orientati che li uniscono, e supponendo di memorizzare le liste di adiacenza nellordine 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 {\displaystyle m\,\log _{2}n}

Questo costo è in generale sub-ottimale. Tuttavia può essere un buon risultato se si deve memorizzare grafi sparsi con m tipicamente dellordine 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ì lefficienza. 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 lefficienza in termini di tempo, la rappresentazione per liste di adiacenza si comporta piuttosto bene sia nellaccesso che nellinserimento, effettuando le operazioni principali in tempo O n {\displaystyle On}.

                                     

2. Sparsità

È 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.