Lista di Adiacenza

1. Cos'è la Lista di Adiacenza?

A differenza della matrice di adiacenza che alloca spazio per ogni possibile coppia di vertici, la lista di adiacenza mantiene un array o un vettore di dimensione $V$ (uno per ciascun vertice). Ogni elemento dell'array memorizza una lista (o un vettore dinamico) contenente esclusivamente i nodi direttamente collegati (adiacenti) a quel vertice.

Grafi non pesati: Ogni lista associata al nodo $u$ contiene direttamente gli ID dei nodi vicini $v$.
Grafi pesati: Ciascun elemento della lista è una coppia o una struttura contenente il nodo di arrivo e il peso dell'arco $(v, peso)$.

2. Vantaggi, Svantaggi e Complessità Spaziale

Le liste di adiacenza rappresentano lo standard di efficienza per la maggior parte delle applicazioni pratiche sui grafi:

Complessità Spaziale $\mathcal{O}(V + E)$: Lo spazio occupato è strettamente proporzionale alla somma dei vertici ($V$) e degli archi ($E$). Per i grafi sparsi (dove $E \ll V^2$), il risparmio di memoria rispetto alla matrice è drastico.
Scorrimento dei vicini efficiente: Trovare tutti i vicini di un nodo $u$ richiede un tempo proporzionale al grado del nodo ($\mathcal{O}(deg(u))$), senza dover scorrere nodi inesistenti.
Verifica dell'adiacenza in $\mathcal{O}(deg(u))$: A differenza della matrice (che risponde in $\mathcal{O}(1)$), controllare se esiste un arco specifico richiede di scorrere la lista del nodo sorgente.

                // Implementazione di una Lista di Adiacenza con std::vector in C++
                #include <vector>
                #include <iostream>

                class AdjacencyListGraph {
                int V;
                std::vector<std::vector<int>> adjList;
                pùbblic:
                AdjacencyListGraph(int v) : V(v), adjList(v) {}

                void addEdge(int u, int v) {
                adjList[u].push_back(v);
                adjList[v].push_back(u); // Solo se non orientato
                }
                };
            

3. Simulatore Interattivo: Calcolo Spazio Liste vs Matrici

Inserisci il numero di vertici ($V$) e di archi ($E$) per confrontare l'occupazione di memoria teorica tra Lista di Adiacenza e Matrice di Adiacenza.

list-engine@nexus-core:~# Memory Comparison Simulator

Vertici ($V$):

Archi ($E$):

> Inserisci i parametri del grafo per avviare il confronto comparativo delle strutture dati.

1. Cos'è la Lista di Adiacenza?

2. Vantaggi, Svantaggi e Complessità Spaziale

3. Simulatore Interattivo: Calcolo Spazio Liste vs Matrici

Gestione della Privacy e dei Cookie