Struttura dei dati del grafico e Algorithms (Esempio)
Sara Chen
Cos'è un grafico nella struttura dei dati?
Un grafico è una struttura dati non lineare costituita da vertici e spigoli, dove i vertici contengono informazioni o dati e gli spigoli funzionano come collegamento tra coppie di vertici.
Viene utilizzato per risolvere problemi reali come trovare il percorso migliore per raggiungere la destinazione e il percorso per le telecomunicazioni e i social network. Gli utenti sono considerati un nodo nel grafico e i fili sono i bordi che collegano gli utenti.
Se gli spigoli sono rappresentati come E e i vertici sono rappresentati come V, allora il grafico G può essere scritto come l'insieme di vertici e spigoli, come ad esempio G (V, E)
Esempio di grafico nella struttura dei dati
Ecco un semplice esempio di struttura dei dati del grafico:
È un semplice grafico non orientato (un tipo di grafico). Qui l'insieme dei vertici è: {A, B, C,D,E,F}. Due vertici creano un bordo. Ad esempio, A e B sono collegati da un bordo. Tuttavia, A e F non sono collegati ad alcun arco.
Terminologie dei grafici nella struttura dei dati
Di seguito sono riportati alcuni termini importanti utilizzati nella struttura dei dati grafici:
| Termine | Descrizione |
|---|---|
| Vertice | Tutti gli elementi dati sono chiamati vertice o nodo. Nell'immagine sopra, A, B, C, D ed E sono i vertici. |
| Bordo (arco) | I collegamenti tra due nodi o vertici sono chiamati bordo (arco). Ha due estremità ed è rappresentato come (vertice iniziale, vertice finale). |
| Bordo non orientato | È un vantaggio bidirezionale. |
| Bordo diretto | È un bordo unidirezionale. |
| Bordo ponderato | Un vantaggio con valore su di esso. |
| Laurea | In Graph, il numero di archi collegati a un vertice è chiamato grado. |
| Ingrado | Il numero totale di spigoli entranti collegati a un vertice. |
| Grado superato | Il numero totale di archi uscenti collegati a un vertice. |
| Auto-ciclo | Un arco si dice autoanello se i suoi due estremi coincidono. |
| Adiacenza | I vertici si dicono adiacenti se hanno uno spigolo connesso. |
Tipi di grafici nella struttura dei dati
Ecco l'elenco dei più comuni tipi di grafici nella struttura dati:
- Grafico diretto
- Grafico non orientato
- Grafico ponderato
- Grafico bidirezionale
- Grafico infinito
- Grafico nullo
- Grafico banale
- Grafico multiplo
- Grafico completo
- Grafico connesso
- Grafico ciclico
- Grafico aciclico diretto (DAG)
- Grafico del ciclo
- Grafico bipartito
- Grafico di Eulero
- Grafico di Hamilton
Applicazioni della struttura dei dati del grafico
Un grafico ha molti casi d'uso. Esistono molti algoritmi che utilizzano molto i grafici. Ecco alcune delle applicazioni del grafico:
- Google Maps utilizza i grafici per trovare l'intersezione di due strade e calcolare la distanza tra due posizioni.
Per esempio, Dijkstra, per trovare la distanza più breve tra la posizione di origine e quella di destinazione. - Facebook utilizza i grafici per trovare l'amico comune degli utenti. Il suo algoritmo considera ogni utente come un nodo di un grafico.
- Per l'allocazione delle risorse viene utilizzato il DAG (Direct Acyclic Graph). Controlla la dipendenza delle risorse.
- Il motore di ricerca di Google utilizza i grafici per creare la classifica dei siti web.
- Un dispositivo di mappatura utilizza la struttura dei dati del grafico.
- router e il protocollo di t utilizza il grafico per apprendere il percorso del percorso di destinazione.
