La lista e la matrice delle adiacenze
Per rappresentare un grafo in un programma informatico posso seguire due strade alternative: la matrice di adiacenze e la lista di connessione.
Cos'é un grafo? E' una struttura composta da nodi e archi.
La matrice delle adiacenze ( o matrice di connessione ).
Creo un array V[x][y] a due dimensioni per realizzare una matrice quadrata. Dove x e y sono i nodi del grafo.
Nella matrice le righe sono i nodi di partenza mentre le colonne i nodi di destinazione.
A ogni elemento (x,y) della matrice assegno il valore 1 se i due nodi sono collegati oppure 0 se non lo sono.
Nota. Nel caso del grafo non orientato la matrice di adiacenza è una matrice trasposta. E' quindi inutile e una duplicazione di dati memorizzare tutta la matrice perché la diagonale separa due aree identiche. In questo caso, posso memorizzare soltanto una delle due insieme alla diagonale. In questo modo risparmio spazio di memoria.
La liste delle adiacenze
Ogni nodo è un elemento di una variabile array V[n] a cui assegno la lista delle coppie ordinate che collega.
Differenza tra grafo orientato e non orientato. Nel grafo non orientato ogni arco è una relazione biunivoca. Ad esempio, il nodo 1 è connesso al nodo 2 e viceversa. Nel grafo orientato, invece, ogni arco ha una direzione e, quindi, è una relazione univoca. Ad esempio, il nodo 1 è connesso al nodo 2 ma non viceversa. Gli archi non orientati sono detti spigoli e i loro estremi sono detti vertici anziché nodi.
Quale è meglio usare?
Le liste di adiacenze sono preferibili quando il grafo è sparso, ossia quando il numero degli archi |E| è relativamente piccolo, rispetto al numero dei nodi |V|.
Le matrici sono invece preferibili quando il grafo è denso, ossia quando il numero degli archi |E| ≅ |V|2.
Inoltre, la matrice di adiacenze mi permette subito di capire se due nodi del grafo sono collegati tra loro.
Viceversa, in una lista di adiacenze la ricerca è più lunga.
La matrice di adiacenza ha una complessità temporale di accesso ai dati più bassa rispetto alla lista di adiacenza.
D'altra parte, la matrice di adiacenze occupa più spazio di memoria rispetto alla lista di adiacenze ( 21 contro 15 locazioni di memoria ).
Nel precedente esempio ho considerato soltanto metà matrice perché si tratta di un grafo non orientato. L'altra metà è identica.
Ciò nonostante la matrice occupa più memoria della lista di adiacenze.
Nel caso dei grafi orientati la differenza tra i due metodi è ancora più ampia perché devo memorizzare l'intera matrice, mentre la lista delle adiacenze si riduce.
La matrice di adiacenze dell'esempio precedente occuperebbe ben 36 spazi di memoria contro 8 della lista di adiacenze.
In generale
Lo spazio di memoria di una liste di adiacenze è
- il numero |E| per i grafici orientati
- il doppio 2|E| per i grafici non orientati
Lo spazio di memoria di una matrice di adiacenze è
- il prodotto |V|2 per i grafici orientati
- il numero |V| per i grafici non orientati
Secondo me è particolarmente utile sottolineare un aspetto pratico delle liste
Le liste di adiacenze hanno sempre una complessità θ(V+E) sia per i grafi orientati che per i grafi non orientati
Quindi, se il tempo di ricerca non è un problema, è meglio lavorare con le liste di adiacenze su big data.
