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 (Array e stringhe in CArray di dimensione fissa in memoria contigua, inizializzazione, nessun controllo sugli indici, passaggio a funzioni con la lunghezza, matrici; stringhe come array di char terminati da '\0' e funzioni di string.h.Array e stringhe in C →);
• 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. Le liste sono quelle di Liste, pile e codeRipasso degli ADT elementari: lista index-based (array) e position-based (lista doppiamente concatenata con sentinelle), pila LIFO, coda FIFO, deque, iteratori; interfacce, implementazioni e costi; array estendibile e coda circolare.Liste, pile e code → (Liste concatenate in CLista singolarmente concatenata in C con nodo struct e testa passata per riferimento (Nodo **); addHead, addTail ricorsiva e iterativa, pop, inversione in loco, liberazione; coda con puntatori a testa e coda; ricorsione sulle liste; costi.Liste concatenate in C → per l'implementazione) e i riferimenti tra nodi sono puntatori (Puntatori in CUn puntatore contiene un indirizzo di memoria; operatori & e *, NULL, puntatori come parametri per modificare variabili del chiamante, aritmetica dei puntatori, legame tra array e puntatori, const, puntatori a puntatori.Puntatori in C →).

Liste di adiacenza

Definizione (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, ad esempio Tabelle hashTabella hash per implementare una mappa: funzione hash = hash code + compression function, bucket array, separate chaining; hash code per numeri e stringhe (polynomial, cyclic shift), division e MAD; load factor, complessità al caso pessimo Theta(n) e medio O(1+lambda), rehashing; esempio svolto con inserimenti e collisioni.Tabelle hash →: con una mappa areAdjacent costerebbe $\Theta(1)$ in media). È 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$.

Esempio. Con archi $(1,2),(1,3),(2,3),(3,4)$ e il vertice $5$ isolato: $I(1)=\{2,3\}$, $I(3)=\{1,2,4\}$ e $I(5)=\emptyset$.

Matrice di adiacenza

Definizione (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)$).

Esempio. Con $n=5$ la matrice ha $25$ celle; $A[1,3]$ punta all'arco $(1,3)$ se esiste, altrimenti vale null.

Confronto

Proprietà (spazio e tempi delle rappresentazioni di un grafo)

Operazione / risorsa	Solo $L_E$	Liste di adiacenza	Matrice di adiacenza
spazio	$\Theta(n + m)$	$\Theta(n + m)$	$\Theta(n^2)$
incidentEdges(v)	$\Theta(m)$	$\Theta(\text{degree}(v))$	$\Theta(n)$
opposite(v, e)	$\Theta(1)$	$\Theta(1)$	$\Theta(1)$
areAdjacent(u, v)	$\Theta(m)$	$\Theta(\min(\text{degree}(u), \text{degree}(v)))$	$\Theta(1)$
scansione di tutti i vicini di tutti i vertici	$\Theta(nm)$	$\Theta(n + m)$	$\Theta(n^2)$

Esempio. Con $n=1000$ vertici e $m=3000$ archi le liste di adiacenza usano $\Theta(n+m)=4000$ celle (più precisamente $n+2m=7000$ riferimenti, perché ogni arco è in due liste), la matrice $n^2=10^6$.

Come si legge la tabella. incidentEdges(v) con sola $L_E$ costringe a guardare tutti gli $m$ archi per trovare quelli incidenti su $v$; con le liste basta percorrere $I(v)$, lunga $\text{degree}(v)$; con la matrice si legge tutta la riga $v$ ($n$ celle, quasi tutte vuote in un grafo sparso). areAdjacent(u,v) con le liste si fa scorrendo in parallelo $I(u)$ e $I(v)$ e fermandosi appena una finisce, quindi in $\Theta(\min(\text{degree}(u),\text{degree}(v)))$; con la matrice si legge la cella $A[u,v]$, un solo accesso diretto ($\Theta(1)$ come l'indicizzazione di un array nel modello RAM, Problemi computazionali e algoritmiProblema computazionale come insieme di coppie (istanza, soluzione); algoritmo e modello di calcolo RAM; pseudocodice; taglia di un'istanza; ADT e struttura dati concreta; esempio svolto con ricerca lineare e binaria in un array ordinato.Problemi computazionali e algoritmi →). Il grafico confronta lo spazio per un grafo sparso con $m=3n$ (ogni vertice ha in media grado $6$):

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; per un grafo non diretto è simmetrica, $A=A^{T}$, perché l'arco $(i,j)$ è lo stesso di $(j,i)$: Operazioni tra matriciLe matrici m×n formano uno spazio vettoriale (somma e prodotto per scalare elemento per elemento); il prodotto righe per colonne corrisponde alla composizione di funzioni lineari, è associativo ma non commutativo; la trasposta scambia righe e colonne e (AB)^T = B^T A^T.Operazioni tra matrici →; la somma della riga $i$ è il grado di $i$, quella di tutte le righe $2m=8$):

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))$.