Lista di adiacenze e rappresentazione matriciale del grafico

⚡ Riepilogo intelligente

Le rappresentazioni a lista di adiacenza e a matrice di adiacenza dei grafi memorizzano vertici e archi in memoria, consentendo agli algoritmi di attraversare le reti. La lista di adiacenza utilizza liste concatenate per ogni vertice, mentre la matrice di adiacenza utilizza una griglia quadrata bidimensionale.

📐 Elenco di adiacenza: Un array di V liste concatenate in cui ogni lista all'indice i memorizza ogni vertice adiacente al vertice i, fornendo una memoria O(V + E).
️ Matrice di adiacenza: Array bidimensionale AV × V in cui matrix[i][j] contiene il peso dell'arco o 1 quando esiste un arco tra il vertice i e il vertice j.
⚡ Velocità di ricerca: La matrice di adiacenza risponde alla domanda "esiste un arco tra i e j?" in tempo O(1), mentre la lista di adiacenza richiede un tempo O(grado) per scansionare la lista dei vicini.
💾 Memoria: La matrice di adiacenza consuma sempre O(V²) memoria anche per i grafi sparsi, mentre una lista di adiacenza scala in base al numero effettivo di archi.
🔍 migliore vestibilità: Scegli la matrice di adiacenza per grafi densi con frequenti interrogazioni sugli archi e la lista di adiacenza per grafi sparsi e carichi di lavoro con un elevato numero di attraversamenti.
️ applicazioni: Entrambe le rappresentazioni sono alla base di algoritmi come BFS, DFS, Dijkstra, PageRank, routing su rete stradale e pipeline di reti neurali a grafo utilizzate nei sistemi di intelligenza artificiale.

Scopri di più

Anche se sembrano diversi, tutti tipi di grafici possono essere rappresentati in modo simile. Esistono generalmente due tipi di rappresentazione grafica:

Matrice di adiacenza
Elenco di adiacenza

Elenco di adiacenza

Una lista di adiacenza è composta da liste concatenate. Ogni vertice è considerato un indice di un array e ogni elemento rappresenta una lista concatenata. Queste liste concatenate contengono i vertici che condividono un arco con il vertice indice.

Ecco un esempio di lista di adiacenza:

Sia V il numero di vertici e E il numero di archi del grafo. La complessità spaziale della lista di adiacenza è O(V + E), che scala con il numero di lati reali anziché con ogni possibile coppia di vertici.

La complessità dello spazio nel caso peggiore diventa O(V²) se il grafo dato è un grafo completo, poiché in tal caso ogni vertice si connette a ogni altro vertice.

Matrice di adiacenza

Una matrice di adiacenza è composta da un array 2D. Per un grafo con V vertici, la dimensione della matrice sarà V × V.

Dire matrix[i][j] = 5Significa che esiste un arco tra il nodo i e il nodo j il cui peso è 5.

Osserviamo il seguente grafo e la sua matrice di adiacenza:

Abbiamo costruito il matrice 2D utilizzando questi passaggi:

Passo 1) Il vertice A ha un arco diretto con B e il suo peso è 5. Pertanto, la cella nella riga A e nella colonna B verrà riempita con 5. Le restanti celle nella riga A verranno riempite con 0.

Passo 2) Il vertice B ha un arco diretto con C, e il suo peso è 4. Pertanto, la cella nella riga B e nella colonna C verrà riempita con 4. Le celle rimanenti nella riga B verranno riempite con zeri, poiché B non ha archi uscenti verso nessun altro nodo.

Passo 3) Il vertice C non ha lati diretti con nessun altro vertice. Pertanto, la riga C sarà riempita di zeri.

Passo 4) Il vertice D ha un arco orientato con A e C.

La cella nella riga D e nella colonna A avrà il valore 7. La cella nella riga D e nella colonna C avrà il valore 2.
Il resto delle celle nella riga D verrà riempito con zeri.

Passo 5) Il vertice E ha un arco orientato con B e D. La cella nella riga E e nella colonna B avrà il valore 6. La cella nella riga E e nella colonna D avrà il valore 3. Le restanti celle della riga E saranno riempite con zeri.

Ecco alcuni punti da notare:

Il grafo non presenta auto-loop quando la diagonale principale della matrice di adiacenza è pari a 0.
Il grafico è orientato se le celle in (a, b) e (b, a) non hanno lo stesso valore. Altrimenti, il grafico è non orientato.
Il grafico è ponderato se il valore di una qualsiasi cella è maggiore di 1.

Il problema principale della matrice di adiacenza è che richiede uno spazio quadrato. Persino gli archi inesistenti occupano comunque celle di memoria.

Ad esempio, se abbiamo un grafico con 100 nodi, allora sono necessarie 10,000 celle per memorizzarlo in RAMCon un numero inferiore di archi nel grafo, allocare una memoria così grande può essere uno spreco. Quindi la complessità dello spazio utilizzando la matrice di adiacenza è O(N²), dove N è il numero di nodi nel grafo.

Lista di adiacenza vs matrice di adiacenza

Prima di scegliere una rappresentazione, è utile confrontare entrambi i modelli fianco a fianco nelle operazioni che dominano i carichi di lavoro reali sui grafi:

Funzionamento	Matrice di adiacenza	Elenco di adiacenza
Complessità spaziale	O(V²)	O(V + E)
Aggiungi un vertice	O(V²)	O (1)
Aggiungi un bordo	O (1)	O (1)
Rimuovere un bordo	O (1)	O(E)
Verifica se esiste l'arco (i, j)	O (1)	O(grado di i)
Itera sui vicini di i	O(V)	O(grado di i)
migliori per	Grafi densi, frequenti interrogazioni degli archi	Grafi sparsi, attività che richiedono un'intensa attività di attraversamento

In breve, la matrice di adiacenza è più efficiente nelle ricerche sugli archi a tempo costante, mentre la lista di adiacenza è più efficiente in termini di memoria e iterazione dei vicini; ecco perché algoritmi come BFS, DFS e Dijkstra vengono solitamente utilizzati in combinazione con le liste di adiacenza.

Vantaggi e svantaggi della rappresentazione grafica

Ciascuna rappresentazione presenta i propri compromessi. Conoscere i punti di forza e di debolezza di entrambi i modelli aiuta a scegliere quello più adatto al problema da risolvere.

Vantaggi della matrice di adiacenza:

Query di esistenza degli archi in tempo costante O(1) tra qualsiasi coppia di vertici.
L'indicizzazione fissa semplifica l'implementazione di algoritmi basati su matrici, come quelli di Floyd-Warshall e della chiusura transitiva.
I bordi ponderati si adattano naturalmente a una singola cella della matrice.

Svantaggi della matrice di adiacenza:

Spreca memoria O(V²) quando il grafo è sparso.
L'aggiunta di un nuovo vertice richiede il ridimensionamento dell'intera matrice.
L'iterazione sui vicini di un singolo vertice richiede O(V) anche quando il vertice ha solo pochi lati.

Vantaggi della lista di adiacenza:

Utilizza solo O(V + E) di memoria, che è vicino al numero reale di archi nei grafi sparsi.
L'aggiunta di un nuovo vertice o di un nuovo arco è O(1).
Gli algoritmi di attraversamento come BFS e DFS iterano i vicini in O(grado), fornendo un tempo di esecuzione complessivo di O(V + E).

Svantaggi della lista di adiacenza:

Verificare se un determinato arco esiste richiede un tempo O(grado) anziché O(1).
La località della cache è più debole perché le liste concatenate sono sparse nella memoria.
Gli archi ponderati richiedono un campo associato o un elenco di coppie, il che complica leggermente la struttura dei dati.

Quando utilizzare la lista di adiacenza rispetto alla matrice di adiacenza

La scelta della rappresentazione dipende dalla densità del grafo e dalle operazioni che si eseguono più frequentemente. Utilizza questa breve guida per scegliere la struttura più adatta:

Preferisci la matrice di adiacenza quando il grafo è denso (E è vicino a V²), quando gli archi cambiano raramente e quando il tuo algoritmo chiede "esiste un arco tra i e j?" molte volte.
Preferisci l'elenco di adiacenza quando il grafo è sparso (E è molto più piccolo di V²), quando l'insieme dei vertici o degli archi cresce durante l'esecuzione e quando si attraversa il grafo con BFS, DFS o Algoritmo del percorso più breve di Dijkstra.
Preferire un modello misto (lista di adiacenza più un insieme hash di archi) quando hai bisogno sia di un'iterazione veloce dei vicini che di query sugli archi O(1), a costo di memoria aggiuntiva.

Le moderne librerie per la gestione dei grafi, come NetworkX e igraph, utilizzano di default le liste di adiacenza perché la maggior parte dei grafi reali (social network, mappe stradali, pagine web, dipendenze tra pacchetti) sono sparsi e richiedono un'intensa attività di attraversamento.

DOMANDE FREQUENTI

Una lista di adiacenza è un array di V liste concatenate in cui ogni lista all'indice i memorizza ogni vertice adiacente al vertice i. L'utilizzo della memoria è O(V + E), il che la rende adatta a grafi sparsi e algoritmi di attraversamento come BFS e DFS.

Una matrice di adiacenza è un array bidimensionale V × V in cui matrix[i][j] contiene il peso dell'arco o 1 se esiste un arco tra il vertice i e il vertice j. La ricerca di un arco è O(1), ma la memoria è sempre O(V²).

La matrice di adiacenza risponde alle query di esistenza degli archi in O(1). La lista di adiacenza itera i vicini in O(grado), il che è più veloce per algoritmi di attraversamento come BFS, DFS e Dijkstra. La scelta migliore dipende dalle operazioni che dominano il carico di lavoro.

È utile utilizzare una lista di adiacenza quando il grafo è sparso, quando vertici e archi cambiano durante l'esecuzione e quando l'algoritmo attraversa frequentemente i nodi vicini. I social network, le mappe stradali e i grafi delle pagine web rientrano tutti in questo profilo.

È consigliabile utilizzare una matrice di adiacenza quando il grafo è denso, quando l'insieme dei vertici è fisso e quando l'algoritmo interroga ripetutamente lo stesso arco. Sia l'algoritmo di Floyd-Warshall che la chiusura transitiva funzionano naturalmente sulle matrici di adiacenza.

Sì. Nei grafi diretti la matrice non è simmetrica e la lista memorizza solo i vicini uscenti. Nei grafi pesati la cella della matrice contiene il peso mentre la lista memorizza le coppie vicino-peso.

Le reti neurali a grafo alimentano i livelli di apprendimento automatico con matrici di adiacenza o tensori di archi sparsi per il rilevamento delle frodi, la previsione delle proprietà molecolari e i sistemi di raccomandazione. I grafi della conoscenza si basano anche su codifiche di liste di adiacenza per l'intelligenza artificiale potenziata dal recupero delle informazioni.

Sì. GitHub Copilot e ChatGPT generano lista di adiacenza e boilerplate di matrice per Python, C++e JavaGli sviluppatori devono ancora verificare i casi limite, come archi duplicati, auto-loop e la corretta gestione dei grafi diretti o pesati.