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.).
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).Diverse strutture dati vengono usate in pratica per l'implementazione dei grafi:
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.