Struttura dei dati del grafico e Algorithms (Esempio)
Sara Chen
⚡ Riepilogo intelligente
La struttura dati a grafo è una collezione non lineare di vertici e archi, dove ogni arco collega una coppia di vertici. I grafi modellano reti del mondo reale come mappe, connessioni sociali e pagine web, e supportano molti potenti algoritmi.
Cos'è un grafico nella struttura dei dati?
Un grafo è una struttura dati non lineare composta da vertici e archi, dove i vertici contengono le informazioni o i dati e gli archi fungono da collegamento tra una coppia di vertici.
Viene utilizzato per risolvere problemi del mondo reale, come trovare il percorso migliore per raggiungere la destinazione e il percorso per le telecomunicazioni e i social network. Gli utenti sono considerati nodi nel grafo e i fili sono gli archi che li collegano.
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 dati a grafo:
Si tratta di un semplice grafo non orientato (un tipo di grafo). L'insieme dei vertici è: {A, B, C, D, E, F}. Due vertici formano un arco. Ad esempio, A e B sono collegati da un arco. Tuttavia, A e F non sono collegati da alcun arco.
Terminologie dei grafici nella struttura dei dati
Di seguito sono riportati alcuni termini importanti utilizzati nella struttura dati a grafo:
| Termine | Descrizione |
|---|---|
| Vertice | Ciascun elemento di dati è chiamato 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 archi (o lati). Hanno due estremità e sono rappresentati come (verticeiniziale, verticefinale). |
| Bordo non orientato | È un vantaggio bidirezionale. |
| Bordo diretto | È un bordo unidirezionale. |
| Bordo ponderato | Un vantaggio che ha un valore intrinseco. |
| Laurea | In un grafo, 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 | Si dice che due vertici sono adiacenti se un lato li collega. |
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
Come rappresentare un grafico in una struttura dati?
Un grafo viene generalmente memorizzato in memoria utilizzando una delle due rappresentazioni. La scelta influisce sulla quantità di memoria utilizzata dal grafo e sulla velocità di esecuzione delle operazioni più comuni.
- Matrice di adiacenza: Una matrice bidimensionale V × V in cui la cella [i][j] è 1 (o il peso dell'arco) se esiste un arco tra il vertice i e il vertice j, e 0 altrimenti. Consente la ricerca di archi in O(1) ma utilizza uno spazio O(V²), risultando quindi ideale per grafi densi.
- Elenco di adiacenza: Un array di liste in cui ogni vertice memorizza una lista dei suoi vertici vicini. Utilizza uno spazio O(V + E) ed è efficiente per i grafi sparsi, motivo per cui la maggior parte dei grafi del mondo reale lo utilizza.
Puoi leggere di più su questi nel lista di adiacenza e rappresentazione matriciale di un grafo tutorial.
Applicazioni della struttura dei dati del grafico
Un grafo ha molteplici utilizzi. Esistono numerosi algoritmi che si avvalgono dei grafi. Ecco alcune delle applicazioni dei grafi:
- Google Le mappe utilizzano grafici per trovare l'intersezione di due strade e calcolare la distanza tra due posizioni. Ad esempio, Dijkstraper trovare la distanza più breve tra il punto di partenza e quello di destinazione.
- Facebook utilizza i grafi per trovare gli amici in comune degli utenti. Il suo algoritmo considera ogni utente come un nodo di un grafo.
- Per l'allocazione delle risorse, viene utilizzato un DAG (grafo aciclico diretto) che verifica le dipendenze tra le risorse.
- Migliori Google I motori di ricerca utilizzano grafici per creare una classifica dei siti web.
- Una cartinaping Il dispositivo utilizza la struttura dati a grafo.
- A router e il suo protocollo utilizzano il grafo per apprendere il percorso verso la destinazione.
