Rappresentazione di grafi
Liste di adiacenza
Matrice di adiacenza
Matrice di incidenza
Rappresentazione di grafi
Vi sono diversi modi per rappresentare un grafo G=(V,E):
come una collezione di liste di incidenza o come una matrice
di adiacenza o come una matrice di incidenza.
Di solito si preferisce la rappresentazione con liste di
adiacenza perché quando il grafo è sparso, |E| molto
minore di |V|2, fornisce una rappresentazione compatta del
grafo.
Se invece il grafo è denso , |E| è vicino a |V|2, la matrice di
adiacenza può essere preferita, perché è più rapido
accedere all’informazione in essa contenuta. Per esempio
sapere se due archi sono adiacenti.
Liste di adiacenza
Consiste in un vettore Adj di |V| liste, una per ogni vertice
di V. Per ogni u in V, la lista di adiacenza Adj[u] comprende
tutti i gli archi (u,v) in E, con v in V e adiacente a u.
La quantità di memoria necessaria è O(max(|V|,|E|)) =
O(|V|+|E|).
nodo
adiacente
Grafo non orientato
next
Adj[1,…,6]
1
2
3
6
4
5
1
2
3
2
1
3
3
1
2
4
3
5
---
5
4
6
---
6
1
5
---
6
---
4
---
---
Liste di adiacenza
Se ci sono dei pesi sui vertici vengono memorizzati nel
vettore Adj insieme al puntatore all’inizio della lista di
adiacenza.
Se c’è un peso w su un arco (u,v) viene memorizzato nel
corrispettivo elemento della lista di adiacenza Adj[u].
nodo
adiacente
Grafo orientato
next
Adj[1,…,6]
1
2
3
2
2
3
---
4
3
---
5
6
3
6
4
1
5
3
---
4
6
---
1
5
---
---
Matrice di adiacenza
Si assume che i vertici siano numerati 1, 2, …, |V| in modo
arbitrario. La matrice di adiacenza consiste in una matrice
A=(aij) di dimensione |V| x |V| tale che:
1 se (i, j)  E
aij  
 0 altrimenti
1
Grafo non orientato
1
2
A=
3
6
4
2
3
4
5
6
1
0 1 1 0 0 1
2
1 0 1 0 0 0
3
1 1 0 1 0 0
4
0 0 1 0 1 0
5
0 0 0 1 0 1
6
1 0 0 0 1 0
5
Matrice di adiacenza
Nel caso di un grafo non orientato la matrice A risulta
simmetrica, A=AT, ossia aij = (aij)T = aji.
La matrice richiede memoria Θ(|V|2).
E’ possibile anche memorizzare il peso di ogni arco nella
rispettiva cella aij.
1
Grafo orientato
1
2
A=
3
6
4
2
3
4
5
6
1
0 1 1 0 0 0
2
0 0 1 0 0 0
3
0 0 0 0 0 0
4
0 0 1 0 0 0
5
0 0 0 1 0 1
6
1 0 0 0 1 0
5
Matrice di incidenza
Si assume che i vertici siano numerati 1, 2, …, |V| in modo
arbitrario. La matrice di adiacenza consiste in una matrice
D=(dij) di dimensione |V| x |E| tale che:
 1 se e j entra in vi

d ij   1 se e j esce da vi
0
altrimenti

Grafo orientato
1
1
2
D=
3
7
4
4
5
6
6
5
3
4
5
6
7
1
-1 -1 0
0
0
0
0 +1
2
+1 0 -1 0
0
0
0
0
3
0 +1 +1 +1 0
0
0
0
4
0
0
0 -1 +1 0
0
0
5
0
0
0
0 -1 -1 +1 0
6
0
0
0
0 0 +1 -1 -1
1
8
3
2
La matrice richiede
memoria Θ(|V|x|E|).
2
8