Visualizza wikitesto di Grafo (tipo di dato astratto)

{{S|teoria dei grafi}}
[[File:Directed.svg|miniatura|125x125px|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|grafo non orientato]] (indiretto) e [[Digrafo (matematica)|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:
* <code>adiacente</code>(''G'', ''x'', ''y''): verifica se esiste un arco dal nodo ''x'' al nodo ''y'';
* <code>vicini</code>(''G'', ''x''): elenca tutti i vertici y tali che esiste un arco dal nodo ''x'' al nodo ''y'';
* <code>aggiungi_nodo</code>(''G'', ''x''): aggiunge il nodo ''x'' se non è già presente;
* <code>rimuovi_nodo</code>(''G'', ''x''): rimuove il nodo ''x'' se presente;
* <code>aggiungi_arco</code>(''G'', ''x'', ''y''): aggiunge l'arco dal nodo ''x'' al nodo ''y'' se non è già presente;
* <code>rimuovi_arco</code>(''G'', ''x'', ''y''): rimuove l'arco dal nodo ''x'' al nodo ''y'' se presente;
* <code>ottieni_valore_nodo</code>(''G'', ''x''): restituisce il valore associato al nodo ''x'';
* <code>imposta_valore_nodo</code>(''G'', ''x'', ''v''): imposta il valore ''v'' al nodo ''x''.
Strutture che associano valori agli archi solitamente forniscono anche:
* <code>ottieni_valore_arco</code>(''G'', ''x'', ''y''): restituisce il valore associato all'arco (''x'', ''y'');
* <code>imposta_valore_arco</code>(''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 (informatica)|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 delle adiacenze|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 ∞
{| class="wikitable"
!
!Lista di adiacenza
!Matrice di adiacenza
!Matrice di incidenza
|-
|Memorizzare il grafo
|<math>O(|V|+|E|)</math>
|<math>O(|V|^2)</math>
|<math>O(|V|\cdot|E|)</math>
|-
|Aggiungere un vertice
|<math>O(1)</math>
|<math>O(|V|^2)</math>
|<math>O(|V|\cdot|E|)</math>
|-
|Aggiungere un arco
|<math>O(1)</math>
|<math>O(1)</math>
|<math>O(|V|\cdot|E|)</math>
|-
|Rimuovere un vertice
|<math>O(|E|)</math>
|<math>O(|V|^2)</math>
|<math>O(|V|\cdot|E|)</math>
|-
|Rimuovere un arco
|<math>O(|E|)</math>
|<math>O(1)</math>
|<math>O(|V|\cdot|E|)</math>
|-
|Query: i vertici ''x'' e ''y'' sono adiacenti? (assumendo che le loro posizioni siano note)
|<math>O(|V|)</math>
|<math>O(1)</math>
|<math>O(|E|)</math>
|-
|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''|<sup>2</sup>, 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 ==
{{interprogetto|preposizione=sul}}

{{Strutture dati}}
{{portale|informatica}}

[[Categoria:Teoria dei grafi]]