giovedì 15 marzo 2018

Rappresentazione dei grafi attraverso strutture dati

Esistono due modi per rappresentare un grafo $G$ di $V$ vertici ed $E$ archi (indicato con $G = (V, E)$), ed entrambi permettono di descrivere qualsiasi tipo di grafo: orientato o meno, pesato o meno, collegato o meno, denso o sparso, e così via.




Uno di questi due metodi prevede l'uso di matrici $|V|\times |V|$.
Per un grafo non orientato si nota che la matrice è simmetrica rispetto alla diagonale dato che un arco appare due volte per ogni coppia di vertici (si confrontino le immagini a sinistra riportate nelle figure sopra e sotto questo paragrafo).
Questa rappresentazione non è molto usata, almeno in ambito gaming, fondamentalmente perché richiede abbastanza spazio in memoria $(|V|^2)$ per grafi molti grandi, anche se usare singoli bit per memorizzare il collegamento di due vertici è un'ottimizzazione che fa risparmiare molta memoria. L'uso di attributi per vertici o archi (ad esempio il peso di un arco per grafi pesati) in genere può richiede semplicemente la memorizzazione dell'attributo nell'elemento riservato al collegamento dei due vertici (al posto dell'$1$ che rappresenta l'arco nell'immagine sotto) oppure può richiedere l'uso di matrici addizionali della stessa dimensione $|V|\times |V|$.




L'altro metodo per rappresentare i grafi prevede l'uso di liste di adiacenza. Si tratta semplicemente di un array di liste concatenate singolarmente. E' il metodo più usato data la sua versatilità e lo spazio relativamente contenuto che [ richiesto per l'archiviazione dei dati in presenza di grafi grandi ma non troppo densi. Dato che ogni vertice può essere collegato a più vertici, se si usano i vertici stessi come elementi delle liste si verrebbero a creare istanze multiple di uno stesso vertice (il che non è mai consigliabile). Si possono, invece, usare puntatori ai vertici come elementi delle liste. In questo modo si evita di avere più istanze di uno stesso vertice ed in più avrebbe maggior senso a livello logico nel caso in cui si volesse che gli elementi delle liste rappresentino gli archi tra i vertici piuttosto che i vertici stessi.
Se ci sono attributi da memorizzare per vertici o archi questi possono essere inseriti come variabili di istanza all'interno dei vertici o degli elementi delle liste, rispettivamente. Questo perché per gli archi, come già detto, ogni elemento della lista di adiacenza relativo ad un vertice $u$, identifica non solo il vertice collegato ad $u$ ma anche il suo collegamento con esso (l'arco tra i due).
Oppure, volendo, si può creare un array addizionale di dimensione $|V|$ per gli attributi di vertice.
Nell'immagine sotto si può vedere la rappresentazione con liste di adiacenza del grafo non orientato relativo alla prima immagine (a sinistra).




Nell'immagine sotto, invece, si può vedere la rappresentazione con liste di adiacenza del grafo orientato relativo alla prima immagine (a destra).




Riferimenti:
[1] Introduzione agli algoritmi e strutture dati - Cormen, Leiserson, Rivest, Stein

Nessun commento:

Posta un commento