Топ-100
Indietro

ⓘ Grafo, tipo di dato astratto. In informatica, un grafo è un tipo di dato astratto che viene usato per implementare i concetti di matematica di grafo non orienta ..




Grafo (tipo di dato astratto)
                                     

ⓘ Grafo (tipo di dato astratto)

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

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 unetichetta simbolica o un attributo numerico.

                                     

1. Operazioni

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

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

Strutture che associano valori agli archi solitamente forniscono anche:

  • imposta_valore_arco G, x, y, v: imposta il valore v allarco x, y.
  • ottieni_valore_arco G, x, y: restituisce il valore associato allarco x, y;
                                     

2. Implementazioni

Diverse strutture dati vengono usate in pratica per limplementazione 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 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 le colonne gli archi. Gli ingressi indicano se il vertice in una riga è incidente con larco 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 ∞

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.

                                     
  • albero è un grafo non orientato nel quale due vertici qualsiasi sono connessi da uno e un solo cammino grafo non orientato, connesso e privo di cicli Si
  • vecchi contenitori. Array Database Lista di strutture dati Modello dei dati Record tipo di dato Tipo di dato Struttura dati persistente Altri progetti
  • un gruppo di Coxeter è un gruppo astratto che ammette una descrizione formale in termini di simmetrie speculari. In realtà, i gruppi finiti di Coxeter
  • Tra di esse: Il complesso delle cricche di un grafo G è un complesso simpliciale astratto X G cvon un simplesso per ogni cricca in G Un grafo semplice
  • di questo tipo poiché i vertici sono etichettati determina unicamente un ordinamento parziale ma esistono più diagrammi corrispondenti ad un dato ordine
  • computazionale o problema astratto è una relazione tra un insieme di istanze e un insieme di soluzioni. Un problema computazionale permette di stabilire formalmente
  • per un anello o per un campo. Nella teoria dei grafi un automorfismo di un grafo è una permutazione dei nodi che preserva gli archi e i non archi. Dunque
  • computazionale di trovare una colorazione di un grafo G dato Diversi settori potrebbero seguire i seguenti approcci: Algoritmi centralizzati Il grafo G è codificato
  • i nodi funzionalità di commutazione. Essa è rappresentabile dunque attraverso un grafo La topologia rappresenta le modalità di interconnessione fisica
  • è, inoltre, una delle implementazioni più efficienti di un tipo di dato astratto chiamato coda di priorità. Le operazioni comuni negli heap sono: Basiche