Grafo (tipo di dato astratto)

Da Wikipedia, l'enciclopedia libera.
Jump to navigation Jump to search
Un grafo diretto con tre vertici e tre archi.

In informatica, un grafo è un tipo di dato astratto che viene usato per implementare i concetti di matematica di grafo non orientato (indiretto) e grafo orientato (diretto).

Una struttura dati grafo consiste in un insieme finito (e forse mutabile) di vertici o nodi, e in un insieme di coppie di questi vertici non ordinate per grafi indiretti, o coppie ordinate per grafi diretti. Queste coppie sono gli archi o spigoli nei grafi non orientati e frecce o archi diretti nei grafi orientati.

Una struttura dati grafo può inoltre associare ad ogni arco un valore o peso, ad esempio un'etichetta simbolica o un attributo numerico (costo, capacità, lunghezza, etc.).

Operazioni[modifica | modifica wikitesto]

Le operazioni base fornite da una struttura dati grafo solitamente includono:

  • adiacente(G, x, y): verifica se esiste un arco dal nodo x al nodo y;
  • vicini(G, x): elenca tutti i vertici y tali che esiste un arco dal nodo x al nodo y;
  • aggiungi_nodo(G, x): aggiunge il nodo x se non è già presente;
  • rimuovi_nodo(G, x): rimuove il nodo x se presente;
  • aggiungi_arco(G, x, y): aggiunge l'arco dal nodo x al nodo y se non è già presente;
  • rimuovi_arco(G, x, y): rimuove l'arco dal nodo x al nodo y se presente;
  • ottieni_valore_nodo(G, x): restituisce il valore associato al nodo x;
  • imposta_valore_nodo(G, x, v): imposta il valore v al nodo x.

Strutture che associano valori agli archi solitamente forniscono anche:

  • ottieni_valore_arco(G, x, y): restituisce il valore associato all'arco (x, y);
  • imposta_valore_arco(G, x, y, v): imposta il valore v all'arco (x, y).

Implementazioni[modifica | modifica wikitesto]

Diverse strutture dati vengono usate in pratica per l'implementazione dei grafi:

Lista di adiacenza
I vertici vengono memorizzati come record o oggetti, ed ogni vertice memorizza una lista dei suoi vertici adiacenti. Questa struttura dati permette la memorizzazione di dati aggiuntivi sui vertici. Dati aggiuntivi possono essere inseriti se anche gli archi sono memorizzati come oggetti, in questo caso ogni vertice memorizza i suoi archi incidenti e ogni arco memorizza i suoi vertici incidenti.
Matrice di adiacenza
Una matrice bidimensionale nella quale le righe rappresentano i vertici di partenza e le colonne i vertici di arrivo. I dati sugli archi e sui vertici vanno memorizzati esternamente. Solo il costo di un arco può essere memorizzato per ogni coppia di vertici.
Matrice di incidenza
Una matrice bidimensionale booleana, nella quale le righe rappresentano i vertici e le colonne gli archi. Gli ingressi indicano se il vertice in una riga è incidente con l'arco in una colonna.

La seguente tabella indica il costo della complessità temporale delle performance di diverse operazioni sui grafi per ognuna di queste implementazioni. |V| è il numero di vertici, |E| il numero degli archi. Nelle implementazioni con matrici gli ingressi rappresentano il costo per percorrere un arco. Il costo degli archi che non sono presenti si assume essere ∞

Lista di adiacenza Matrice di adiacenza Matrice di incidenza
Memorizzare il grafo
Aggiungere un vertice
Aggiungere un arco
Rimuovere un vertice
Rimuovere un arco
Query: i vertici x e y sono adiacenti? (assumendo che le loro posizioni siano note)
Osservazioni Rimozione di vertici e archi lenta, perché è necessario trovare tutti i vertici e gli archi Aggiunta o rimozione di vertici lenta, perché la matrice deve essere ridimensionata/copiata Aggiunta o rimozione di vertici e archi lenta, perché la matrice deve essere ridimensionata/copiata

Le liste di adiacenza sono solitamente la soluzione preferita perché implementano in modo efficiente grafi sparsi. Si preferisce la matrice di adiacenza per i grafi densi, ovvero se il numero di archi |E| è vicino al quadrato del numero dei vertici, |V|2, oppure se si deve essere in grado di verificare velocemente la presenza di un arco tra due vertici.

Voci correlate[modifica | modifica wikitesto]

Informatica Portale Informatica: accedi alle voci di Wikipedia che trattano di informatica