Rappresentazione dei grafi

Sia $G = (V, E)$ con $n$ vertici ed $m$ archi (i vertici si indicano spesso con gli interi $1..n$ o $0..n-1$). Tutte le rappresentazioni partono da due strutture di base:

• lista dei vertici $L_V$: ogni nodo contiene le informazioni di un vertice distinto; con vertici interi può essere un array;
• lista degli archi $L_E$: ogni nodo contiene le informazioni di un arco $e = (u, v)$, compresi i puntatori a $u$ e a $v$.

Ogni vertice o arco può avere campi aggiuntivi (ID, peso, etichette, parent) richiesti dall'algoritmo.

Liste di adiacenza

Per ogni vertice $v$ una lista $I(v)$ di puntatori agli archi di $L_E$ incidenti su $v$ (in alternativa, ai vicini; al posto delle liste si possono usare mappe). È la rappresentazione più usata, e quella assunta se non detto altrimenti, perché:

• occupa spazio lineare nella taglia del grafo, $\Theta(n + m)$ (in un grafo non diretto ogni arco compare nelle liste dei suoi due estremi);
• permette di scorrere i vicini di $v$ in tempo lineare nel grado di $v$.

Matrice di adiacenza

Matrice $A$ di dimensione $n \times n$, con righe e colonne in corrispondenza 1-1 con i vertici (che devono essere rappresentati da interi):

$$A[i_1, i_2] = \begin{cases} \text{puntatore a } e = (i_1, i_2) \in L_E & \text{se l'arco esiste} \\ \text{null} & \text{altrimenti.} \end{cases}$$

Dà accesso a un arco in tempo costante, ma occupa $\Theta(n^2)$, che può essere superlineare nella taglia del grafo: conviene per grafi densi ($m = \Theta(n^2)$).

Confronto

Rappresentare gli archi solo con $L_E$ rende lenti gli algoritmi che esplorano i vicini; per questo le visite (vedi Visite di grafi - BFS e DFSVisite in ampiezza (BFS) e in profondità (DFS) come design pattern; etichette discovery, cross e back edge; BFS tree e distanze; complessità Theta(n+m) con liste di adiacenza; applicazioni (connettività, componenti, spanning tree, cammini minimi non pesati, cicli, vertici a distanza al più d); esempio svolto su un grafo di 7 vertici.Visite di grafi - BFS e DFS →) usano le liste di adiacenza, e le loro complessità $\Theta(n + m)$ dipendono da questa scelta (con la matrice sarebbero $\Theta(n^2)$).

Esempio

Grafo con vertici $1..5$ e archi $e_1 = (1,2)$, $e_2 = (1,3)$, $e_3 = (2,3)$, $e_4 = (3,4)$ (il vertice $5$ è isolato).

• $L_V = [1, 2, 3, 4, 5]$, $L_E = [e_1, e_2, e_3, e_4]$.
• Liste di adiacenza: $I(1) = [e_1, e_2]$, $I(2) = [e_1, e_3]$, $I(3) = [e_2, e_3, e_4]$, $I(4) = [e_4]$, $I(5) = [\,]$. La somma delle lunghezze è $2 + 2 + 3 + 1 + 0 = 8 = 2m$ (somma dei gradi, vedi Grafi - definizioni e proprietàGrafo G=(V,E) diretto e non diretto, grafo semplice e pesato; incidenza, adiacenza, grado; cammini, cicli, sottografi, grafi connessi e componenti connesse; alberi liberi, foreste, spanning tree e spanning forest; proprietà con dimostrazioni (somma dei gradi = 2m, m <= n(n-1)/2, alberi m = n-1, connessi m >= n-1, foreste m <= n-1).Grafi - definizioni e proprietà →).
• Matrice di adiacenza (1 = arco presente):

Numero di vertici isolati (richiesto in un esame): si scorrono i vertici e si contano quelli con lista di adiacenza vuota: $\Theta(n)$ con le liste (non serve guardare gli archi); con la matrice occorrerebbe $\Theta(n^2)$.

Errori comuni

• Usare la matrice di adiacenza per un grafo sparso: spreca spazio ($\Theta(n^2)$ contro $\Theta(n + m)$) e rende le visite quadratiche.
• Dimenticare che in un grafo non diretto ogni arco compare due volte nelle liste di adiacenza (e due volte nella matrice, simmetrica).
• Esprimere il costo dello scorrimento dei vicini come $\Theta(n)$ invece di $\Theta(\text{degree}(v))$.