Video: Lezione 1 - Algoritmi e Strutture Dati - 25 settembre 2018 2024
I grafici sono una forma di struttura dati comune utilizzata negli algoritmi. Vedete grafici usati in luoghi come le mappe per il GPS e tutti i tipi di altri luoghi in cui l'approccio dall'alto in basso di una struttura ad albero non funzionerà.
Un grafico è una sorta di estensione di un albero. Come per gli alberi, hai nodi che si connettono tra loro per creare relazioni. Tuttavia, a differenza degli alberi binari, un grafico può avere più di una o due connessioni. In effetti, i nodi dei grafici hanno spesso una moltitudine di connessioni. Per mantenere le cose semplici, però, considera il grafico mostrato.
In questo caso, il grafico crea un anello in cui A si collega sia a B che a F. Tuttavia, non è necessario che sia così. A potrebbe essere un nodo disconnesso o potrebbe anche connettersi a C. Un grafico mostra la connettività tra i nodi in un modo che è utile per definire relazioni complesse.
I grafici aggiungono anche alcuni nuovi colpi di scena a cui non avresti mai pensato prima. Ad esempio, un grafico può includere il concetto di direzionalità. A differenza di un albero, che ha relazioni padre / figlio, un nodo grafico può connettersi a qualsiasi altro nodo con una direzione specifica in mente. Pensa alle strade di una città. La maggior parte delle strade è bidirezionale, ma alcune sono strade a senso unico che consentono il movimento in un'unica direzione.
La presentazione di una connessione grafica potrebbe non riflettere effettivamente la realtà del grafico. Un grafico può designare un peso per una particolare connessione. Il peso può definire la distanza tra due punti, definire il tempo richiesto per attraversare il percorso o fornire altri tipi di informazioni.
