Sulla carta un grafo è un disegno di punti e linee. In un programma, invece, va trasformato in una struttura dati, e la scelta non è neutra: lo stesso algoritmo può richiedere secondi o ore a seconda di come il grafo è memorizzato. Le rappresentazioni classiche sono tre, e ognuna risponde bene a domande diverse.
Nel seguito n è il numero di vertici e m il numero di archi. Supponiamo che i vertici siano numerati da 0 a n − 1: se nei dati hanno nomi (città, indirizzi IP, nomi utente), il primo passo è costruire un dizionario che associa a ogni nome un intero.
La matrice di adiacenza
È una tabella n × n in cui la cella (i, j) vale 1 se esiste l'arco da i a j e 0 altrimenti. Nei grafi pesati la cella contiene il peso, e un valore speciale (per esempio infinito) indica l'assenza di arco. Nei grafi non orientati la matrice è simmetrica.
Vantaggi:
- sapere se due vertici sono collegati costa un solo accesso, cioè tempo costante;
- aggiungere o togliere un arco è immediato;
- si presta a operazioni algebriche: il prodotto della matrice per sé stessa conta i cammini di lunghezza 2.
Il difetto è la memoria: servono n² celle qualunque sia il numero di archi. Con 100.000 vertici sono 10 miliardi di celle, anche se ogni vertice ha appena una decina di vicini. Inoltre elencare i vicini di un vertice richiede di scorrere un'intera riga, cioè n operazioni.
La matrice conviene quindi per grafi piccoli o densi, e per algoritmi che la usano direttamente, come Floyd-Warshall per i cammini minimi tra tutte le coppie.
Le liste di adiacenza
Per ogni vertice si conserva l'elenco dei suoi vicini. In Python la forma più semplice è una lista di liste:
n = 5
adj = [[] for _ in range(n)]
archi = [(0, 1), (0, 2), (1, 3), (3, 4)]
for u, v in archi:
adj[u].append(v)
adj[v].append(u) # ometti questa riga se il grafo è orientato
Nei grafi pesati ogni elemento diventa una coppia (vicino, peso).
Vantaggi:
- la memoria è proporzionale a n + m, quindi ideale per i grafi sparsi, cioè quasi tutti quelli reali;
- scorrere i vicini di un vertice costa quanto il suo grado, ed è proprio l'operazione che usano visite in ampiezza e profondità, Dijkstra e Prim.
Il prezzo è che verificare se un arco specifico esiste richiede di scorrere la lista. Se questa domanda è frequente si possono usare insiemi invece di liste, ottenendo un controllo in tempo medio costante a fronte di un po' più di memoria.
La lista di archi
È la rappresentazione più spartana: un semplice elenco di coppie (u, v), o di terne (u, v, peso). È esattamente il formato di un file CSV esportato da un database o da uno strumento di analisi di rete.
Non permette di trovare in fretta i vicini di un vertice, ma è perfetta quando l'algoritmo deve esaminare tutti gli archi in blocco. L'algoritmo di Kruskal ordina gli archi per peso e li scorre; Bellman-Ford ripete più volte un passaggio su tutti gli archi. In entrambi i casi la lista di archi è la scelta naturale.
Confronto rapido
| Operazione | Matrice | Liste di adiacenza | Lista di archi |
|---|---|---|---|
| Memoria | n² | n + m | m |
| Esiste l'arco (u, v)? | costante | grado di u | m |
| Elencare i vicini di u | n | grado di u | m |
| Aggiungere un arco | costante | costante | costante |
Una variante compatta per grafi grandi
Quando il grafo è statico e molto grande, le liste di liste sprecano memoria per i puntatori e disperdono i dati. Si usa allora il formato CSR (Compressed Sparse Row): un unico array con tutti i vicini concatenati, vertice dopo vertice, e un secondo array di n + 1 indici che dice dove inizia la sezione di ciascun vertice. I vicini di u stanno tra le posizioni indice[u] e indice[u + 1]. È lo stesso schema usato per le matrici sparse nel calcolo scientifico, ed è molto più rapido da scorrere perché i dati sono contigui in memoria.
Come scegliere in pratica
Alcune regole che funzionano quasi sempre:
- Partite dalle liste di adiacenza: sono la scelta predefinita giusta per la maggior parte dei problemi.
- Usate la matrice se n è piccolo (qualche migliaio al massimo) oppure se il grafo è quasi completo.
- Tenete la lista di archi come formato di ingresso e uscita, e per gli algoritmi che lavorano «per archi».
- Passate a CSR o a librerie specializzate quando il grafo supera i milioni di archi e non cambia nel tempo.
Molti programmi reali tengono più rappresentazioni insieme: per esempio liste di adiacenza per le visite e un insieme di coppie per rispondere in fretta alla domanda «questi due nodi sono collegati?».
In sintesi
- La matrice di adiacenza risponde in tempo costante sull'esistenza di un arco, ma occupa n² celle.
- Le liste di adiacenza occupano spazio proporzionale a n + m e sono la scelta predefinita per grafi sparsi.
- La lista di archi è ideale per i dati grezzi e per algoritmi come Kruskal e Bellman-Ford.
- Per grafi grandi e statici il formato CSR riduce memoria e tempi di accesso.
- La rappresentazione giusta dipende dalle domande che l'algoritmo farà più spesso.
