Tipi di grafici nella struttura dei dati con esempi

⚡ Riepilogo intelligente

Nella struttura dati, i grafi sono insiemi non lineari di vertici e archi, classificati in famiglie come grafi diretti, non diretti, pesati, ciclici, aciclici, completi, connessi, bipartiti, di Eulero e di Hamilton, in base alla loro struttura.

📐 Definizione: Un grafo G = (V, E) è una struttura non lineare in cui V è l'insieme dei vertici ed E è l'insieme degli archi che collegano coppie di vertici.
➡️ Direzione: I grafi orientati utilizzano archi con frecce, con un punto di partenza e di arrivo fissi, mentre i grafi non orientati consentono spostamenti bidirezionali lungo ciascun arco.
️ Peso: Nei grafi pesati viene assegnato un costo numerico a ogni arco, mentre nei grafi non pesati tutti gli archi vengono considerati connessioni di uguale costo.
🔁 cicli: I grafi ciclici contengono uno o più cicli; un grafo aciclico diretto (DAG) vieta i cicli e consente la pianificazione e l'ordinamento topologico.
🔗 Completezza: I grafi completi collegano ogni coppia di vertici, i grafi connessi consentono un percorso tra due vertici qualsiasi e i grafi nulli non hanno archi.
🧩 Tipi speciali: I grafi bipartiti, di Eulero, di Hamilton, multipartiti, ciclici e banali impongono ciascuno una regola specifica su come vengono disposti i vertici e gli archi.

Scopri di più

Un grafo è una struttura dati non lineare composta da vertici e archi. I vertici contengono le informazioni o i dati, mentre gli archi fungono da collegamento tra una coppia di vertici.

I grafi possono essere di diversi tipi, a seconda della posizione dei nodi e degli archi. Ecco alcuni tipi importanti di grafi:

Grafico diretto

Gli archi di un grafo orientato contengono frecce che ne indicano la direzione. La freccia determina dove punta o termina l'arco. Ecco un esempio di grafo orientato.

Grafico diretto

Possiamo andare dal nodo A al nodo D.
Tuttavia, non possiamo andare dal nodo D al nodo A, poiché l'arco punta da A a D.
Dato che il grafico non ha pesi, viaggiare dal vertice A a D avrà lo stesso costo del viaggio da D a F.

Grafico non orientato

Un grafo non orientato contiene archi senza puntatori. Ciò significa che possiamo spostarci in entrambe le direzioni tra due vertici. Ecco un semplice esempio di grafo non orientato.

Grafico non orientato

Nel grafico sopra,

Possiamo spostarci da A a B.
Possiamo anche spostarci da B ad A.
I bordi non contengono direzioni.

Si tratta di un esempio di grafo non orientato con un numero finito di vertici e archi senza pesi.

Grafico ponderato

Un grafo che presenta pesi o costi sugli archi è detto grafo pesato. Il valore numerico rappresenta generalmente il costo di spostamento da un vertice a un altro. Sia i grafi diretti che quelli non diretti possono avere pesi sui loro archi. Ecco un esempio di grafo pesato (diretto).

Grafico diretto con peso

Da A a B c'è un arco, e il peso è 5, il che significa che spostarsi da A a B ci costerà 5.
A punta a B, ma in questo grafico B non ha un arco diretto su A. Quindi, non possiamo spostarci da B ad A.
Tuttavia, se vogliamo spostarci da A a F, ci sono più percorsi. I percorsi sono ADF e ABF. Il percorso ADF costerà (10+11) ovvero 21.
Qui, il percorso ABF costerà (5+15) ovvero 20. Qui stiamo aggiungendo il peso di ciascun arco del percorso.

Ecco un esempio di grafo non orientato con pesi:

Grafico non orientato con peso

Qui il bordo ha peso ma non direzione. Quindi significa che viaggiare dal vertice A a D costerà 10 e viceversa.

Grafico bidirezionale

I grafi bidirezionali e non orientati hanno una proprietà in comune. Ovvero:

In generale, un grafo non orientato può avere un solo arco tra due vertici.

Per esempio:

In questo caso, spostarsi da A a D o da D ad A costerà 10.
In un grafico bidirezionale, possiamo avere due bordi tra due vertici.

Ecco un esempio:

Grafico bidirezionale

Viaggiare da A a D ci costerà 17, ma viaggiare da D ad A ci costerà 12. Pertanto, non possiamo assegnare due pesi diversi se si tratta di un grafo non orientato.

Grafico infinito

Il grafo conterrà un numero infinito di archi e nodi. Se un grafo è infinito ed è anche connesso, conterrà anche un numero infinito di archi. In questo caso, gli archi estesi significano che altri archi potrebbero essere collegati a questi nodi tramite archi. Ecco un esempio di grafo infinito:

Grafico infinito

Grafico nullo

Un grafo nullo contiene solo nodi o vertici, ma nessun arco. Dato un grafo G = (V, E), dove V rappresenta i vertici ed E gli archi, il grafo sarà nullo se il numero di archi E è zero. Ecco un esempio di grafo nullo:

Grafico nullo

Grafico banale

Una struttura dati a grafo è considerata banale se presenta un solo vertice o nodo e nessun arco. Ecco un esempio di grafo banale:

Grafico multiplo

Un grafo è detto multigrafo quando sono presenti più archi tra due vertici, oppure quando un vertice presenta un ciclo. Il termine "ciclo" nella struttura dati a grafo indica un arco che punta allo stesso nodo o vertice. Un multigrafo può essere orientato o non orientato. Ecco un esempio di multigrafo:

Ci sono due archi da B ad A. Inoltre, il vertice E presenta un cappio su se stesso. Il grafo sopra riportato è un grafo orientato senza pesi sugli archi.

Grafico completo

Un grafo è completo se ogni vertice ha archi diretti o non diretti con tutti gli altri vertici. Supponiamo che ci siano V vertici in totale e che ogni vertice abbia esattamente V-1 archi. In questo caso, il grafo sarà detto grafo completo. In questo tipo di grafo, ogni vertice è connesso a tutti gli altri vertici tramite archi. Ecco un esempio di grafo completo con cinque vertici:

Come si può vedere nell'immagine, il numero totale di nodi è cinque e tutti i nodi hanno esattamente quattro lati.

Grafico connesso

Un grafo è detto connesso se, partendo da un nodo o vertice, è possibile raggiungere tutti gli altri nodi a partire da tale nodo. A tal fine, deve esserci almeno un arco tra ogni coppia di nodi o vertici. Ecco un esempio di grafo connesso:

Ecco una spiegazione del grafico connesso sopra riportato:

Ipotizzando che non ci sia alcun collegamento tra C e F, non possiamo spostarci da A a G. Tuttavia, il collegamento da C a F ci permette di raggiungere qualsiasi nodo partendo da un nodo dato.
Un grafico completo è un grafico connesso perché possiamo spostarci da un nodo a qualsiasi altro nodo nel grafico dato.

Grafico ciclico

Un grafico si dice ciclico se contiene uno o più cicli. Ecco un esempio di grafico ciclico:

In questo caso, i vertici A, B e C formano un ciclo. Un grafo può contenere più cicli al suo interno.

Grafico aciclico diretto (DAG)

Un grafo è detto grafo aciclico diretto o DAG se non ci sono cicli al suo interno. Il DAG è importante durante l'esecuzione del Ordinamento topologico o per trovare l'ordine di esecuzione. Il DAG è importante anche per creare sistemi di pianificazione o per analizzare le dipendenze delle risorse, ecc. Tuttavia, il grafo sopra non contiene alcun ciclo al suo interno. Ecco un semplice esempio di grafo aciclico diretto (DAG):

Grafico del ciclo

Un grafo ciclico non è la stessa cosa di un grafo ciclico. In un grafo ciclico, ogni nodo avrà esattamente due archi collegati, il che significa che ogni nodo avrà esattamente due gradi. Ecco un esempio di grafo ciclico:

Grafico bipartito

Questi tipi di Grafici sono tipi speciali di grafi in cui i vertici sono assegnati a due insiemi. Un grafo bipartito deve seguire la regola:

I due insiemi di vertici devono essere distinti, il che significa che tutti i vertici devono essere divisi in due gruppi o insiemi.
I vertici dello stesso insieme non devono formare alcun arco.

Grafico di Eulero

Una struttura dati a grafo è considerata un grafo euleriano se tutti i vertici hanno un grado pari. Il termine grado dei vertici indica il numero di archi che puntano verso un determinato vertice o che partono da esso. Ecco un esempio di grafo euleriano:

Tutti i vertici hanno gradi pari. I vertici A, D, E e H hanno due gradi. Qui, il nodo C ha quattro gradi, che è pari.

Grafico di Hamilton

Un grafo hamiltoniano è un grafo connesso, in cui è possibile visitare tutti i vertici a partire da un dato vertice senza rivisitare lo stesso nodo o utilizzare lo stesso arco. Questo tipo di grafo connesso è noto come "grafo hamiltoniano". Il percorso che si percorre per verificare se un dato grafo è un grafo hamiltoniano o meno è detto percorso hamiltoniano. Ecco un semplice esempio di grafo hamiltoniano:

In questa immagine, possiamo visitare tutti i vertici da qualsiasi nodo nel grafico sopra. Uno dei percorsi può essere ADCHBE. È anche possibile trovare un ciclo hamiltoniano. Un ciclo hamiltoniano inizia e finisce nello stesso vertice. Quindi, il ciclo hamiltoniano sarà ADCHBEA.

DOMANDE FREQUENTI

Un grafo è una struttura dati non lineare composta da vertici (nodi) e archi (collegamenti). I vertici memorizzano i dati e gli archi collegano coppie di vertici, formando reti utilizzate per modellare strade, legami sociali, dipendenze e altro ancora.

I grafi orientati utilizzano archi con frecce che puntano da un punto di partenza a un punto di arrivo, limitando gli spostamenti a quella direzione. I grafi non orientati utilizzano archi senza frecce, consentendo gli spostamenti tra i vertici collegati in entrambe le direzioni.

Un grafo aciclico diretto, o DAG, è un grafo diretto che non contiene cicli. I DAG sono ampiamente utilizzati per la pianificazione delle attività, i sistemi di compilazione, la risoluzione delle dipendenze dei pacchetti e qualsiasi flusso di lavoro che richieda un ordine topologico valido.

Un grafo pesato assegna un peso numerico a ogni arco, che rappresenta distanza, tempo o costo. Gli algoritmi per la ricerca del percorso più breve, come l'algoritmo di Dijkstra, e i protocolli di routing di rete utilizzano grafi pesati per trovare il percorso più efficiente.

Un grafo completo ha un arco tra ogni coppia di vertici. Un grafo connesso necessita solo di un percorso tra ogni coppia. Ogni grafo completo è connesso, ma non ogni grafo connesso è completo.

I grafi bipartiti dividono i vertici in due insiemi disgiunti, con archi che collegano solo i due insiemi. Essi modellano problemi di abbinamento come l'assegnazione di lavoratori a incarichi, studenti a corsi o autisti di servizi di trasporto privato a passeggeri.

Le reti neurali a grafo applicano l'apprendimento automatico ai dati strutturati a grafo per attività come il rilevamento delle frodi, la scoperta di farmaci e i sistemi di raccomandazione. I grafi della conoscenza alimentano la risposta alle domande tramite intelligenza artificiale, mentre i grafi computazionali descrivono ogni passaggio in avanti e all'indietro nell'apprendimento profondo.

Sì. Strumenti di AI Copilot come GitHub Copilot e ChatGPT generano codice standard per BFS, DFS, Dijkstra e ordinamento topologico nella maggior parte dei linguaggi. Gli sviluppatori devono comunque verificare i casi limite, la gestione dei cicli e la complessità per il codice di produzione.