Grafo (tipo di dato astratto)

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

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

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	$O(|V|+|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Aggiungere un vertice	$O(1)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Aggiungere un arco	$O(1)$	$O(1)$	$O(|V|\cdot |E|)$
Rimuovere un vertice	$O(|E|)$	$O(|V|^{2})$	$O(|V|\cdot |E|)$
Rimuovere un arco	$O(|E|)$	$O(1)$	$O(|V|\cdot |E|)$
Query: i vertici x e y sono adiacenti? (assumendo che le loro posizioni siano note)	$O(|V|)$	$O(1)$	$O(|E|)$
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|², oppure se si deve essere in grado di verificare velocemente la presenza di un arco tra due vertici.

Voci correlate

• Base di dati a grafo
• Raffigurazione di un grafo

Altri progetti

Altri progetti

• Wikimedia Commons

• Wikimedia Commons contiene immagini o altri file sul grafo