Rappresentazioni

Un grafo sparso conviene venga rappresentato attraverso una lista di adiacenza attraverso un array di $n=|V|$ celle, in ognuna delle quali c'è una lista concatenata contenente i nodi adiacenti.

Per un grafo denso invece, è più conveniente usare una matrice di adiacenza $A$ di dimensione $|V|\times |V|$, in cui $a_{ij}>0$ rappresenta la presenza di un arco, e che nei grafi non orientati è simmetrica, cioè $A^T=A$.

Un'altra rappresentazione è la matrice di incidenza di dimensione $|V|\times |E|$, in cui $a_{ij}$ assume il valore $-1$ quando l'arco assegnato a $j$ che parte dal nodo $i$ è uscente e il valore $1$ quando è entrante.

Per esempio, il grafo

avrà matrice di incidenza con colonne $(1,2)$, $(3,1)$, $(3,4)$, $(4,1)$ e $(1,4)$: $$A=\left[\begin{array}{ccccc}-1& 1& 0& 1& -1\\ 1& 0& 0& 0& 0\\ 0& -1& -1& 0& 0\\ 0& 0& 1& -1& 1\end{array}\right]$$