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. Un semplice grafo; accanto ad ogni vertice è riportata la sua lista di adiacenze. L'idea della rappresentazione è semplicemente che ad ogni vertice viene associata una lista contenente tutti e soli i vertici tali che esista l'arco da a . 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.