Articolo originale: Data Structures 101: Graphs — A Visual Introduction for Beginners
Impara a conoscere le strutture dati che usi ogni giorno
👋 Benvenuto! Iniziamo con un po' di necessario contesto. Ho qualche domanda per te:
✅ Usi Google Search?
✅ Usi Google Maps?
✅ Usi i siti di social media?
Se la tua risposta è "sì" a una qualsiasi di queste domande, allora hai sicuramente utilizzato i grafi e non lo sapevi nemmeno! Sorpreso? 😲 Lo ero anch'io! Questo articolo ti fornirà un'introduzione visiva al mondo dei grafi, al loro scopo, elementi e tipi.
Queste strutture di dati hanno davvero attirato la mia attenzione grazie alle loro incredibili capacità. Sono così potenti che non immagini nemmeno quanto possano essere diverse le loro applicazioni nel mondo reale. Cominciamo! 😁
🌐 Applicazioni nel Mondo Reale — La Magia Inizia!
I grafi sono usati in diversi settori e campi:
- I sistemi GPS e Google Maps usano i grafi per trovare il percorso più breve da una destinazione a un'altra.
- I Social Network usano i grafi per rappresentare le connessioni tra utenti.
- L'algoritmo di Google Search usa i grafi per determinare la rilevanza dei risultati della ricerca.
- La Ricerca Operativa è un campo che utilizza i grafi per trovare il percorso ottimale per ridurre i costi di trasporto e consegna di beni e servizi.
- Anche la chimica usa i grafi per rappresentare le molecole!!! ❤️
Le loro applicazioni sono fantastiche, vero?
Iniziamo il nostro viaggio attraverso questo mondo! 😄
🔵 Ti Presento i Grafi!
Ora che hai un po' di contesto, iniziamo parlando del loro scopo principale e degli elementi che li costituiscono.
I grafi sono usati per rappresentare, trovare, analizzare e ottimizzare connessioni tra gli elementi (case, aeroporti, luoghi, utenti, articoli ecc.).
Questo è un esempio dell'aspetto di un grafo:
💠 Elementi Costitutivi
Sono sicuro che avrai notato due elementi principali nel diagramma qui sopra: dei cerchi e delle linee spesse che li connettono tra loro. Sono chiamati rispettivamente nodi (nodes) e connessioni (edges).
Entriamo nei dettagli! 👍
- Nodi: sono gli elementi che creano la rete. Potrebbero rappresentare case, luoghi, aeroporti, porti, fermate d'autobus, edifici, utenti, praticamente qualunque cosa tu possa rappresentare come collegata ad altri elementi simili in una rete.
- Connessioni: sono collegamenti tra i nodi. Potrebbero rappresentare strade, voli, percorsi di autobus, una connessione tra due utenti in un social network, o qualunque cosa che potrebbe possibilmente rappresentare una connessione tra nodi nel contesto nel quale stai operando.
😱 Cosa Succede Se Non Ci Sono Connessioni?
Se due nodi non sono collegati tra loro, vuol dire che non esiste connessione diretta tra i medesimi. Ma non ti spaventare! 😩 Potresti essere comunque in grado di andare da un nodo all'altro seguendo una serie di connessioni, come se passassi per diverse strade per raggiungere la tua destinazione finale. 🚛️ 🚛 🚛
Per esempio, nel diagramma qui sotto, sebbene non vi sia diretta connessione tra il nodo viola (a sinistra) e il nodo giallo (a destra), puoi comunque raggiungerlo dal nodo viola passando per il nodo arancione, poi per il nodo rosa, quindi per quello verde e arrivare finalmente al nodo giallo. 🏁
Questo è un aspetto chiave dei grafi, puoi trovare l'elemento desiderato seguendo i percorsi a disposizione.
🌟 Notazione e Terminologia
È molto importante imparare il "linguaggio" formale per lavorare con i grafi:
|V|= Numero totale di vertici (nodi) in un grafo.|E|= Numero totale di connessioni in un grafo.
Nell'esempio che segue, |V| = 6 in quanto ci sono sei nodi (i cerchi) ed |E| = 7 poiché ci sono sette connessioni (le righe).
📚 Tipi di Grafo
I grafi sono classificati in base alle caratteristiche delle loro connessioni. Vediamoli in dettaglio! 😃
1️⃣ Grafi Orientati
Nei grafi orientati, le connessioni hanno una direzione. Vanno da un nodo all'altro, e non c'è modo di tornare al nodo iniziale usando quella connessione.
Come puoi vedere nel diagramma qui sotto, le connessioni ora hanno delle frecce che puntano verso una specifica direzione. Pensa a queste connessioni come a strade a senso unico. Puoi andare in una direzione per raggiungere la tua destinazione, ma non puoi tornare indietro facendo la stessa strada, devi cercare un percorso alternativo.
🍕 Per esempio se per un servizio di consegna pizza a domicilio creiamo un grafo che rappresenta una città, due case (i nodi) potrebbero essere connesse da una strada a senso unico. Potresti andare dalla casa A alla casa B passando per questa strada, ma non potresti ritornare, quindi dovresti utilizzare un percorso alternativo.
💡 Nota: In un grafo orientato, potresti non essere in grado di ritornare al tuo luogo di partenza in alcun modo se non esiste un percorso con le direzioni appropriate. 😞 Nel diagramma che segue, puoi notare che puoi andare dal nodo viola a quello verde, ma puoi vedere anche che non c'è modo di tornare dal nodo verde a quello viola, in quanto le connessioni sono "strade a senso unico".
2️⃣ Grafi Non Orientati
In questo tipo di grafi, le connessioni non sono orientate (non hanno una direzione specifica). Pensa a questo tipo di connessioni come a strade a doppio senso. Puoi andare da un nodo all'altro e tornare indietro usando lo stesso "percorso".
💡 Nota: Quando vedi un diagramma di un grafo dove le connessioni non hanno frecce che puntano verso una specifica direzione, puoi assumere che il grafo non è orientato.
🍕 Per il nostro servizio di consegna pizze a domicilio significherebbe che il veicolo per le consegna può andare dalla sorgente alla destinazione e tornare indietro usando la stessa strada o percorso (con sollievo del guidatore! 😇).
Nel grafo qui sotto potresti andare dal nodo viola a quello verde e tornare indietro seguendo lo stesso percorso, quindi non raggiungerai un punto di non ritorno. 😌
🏋 Pesi? — Sì, Pesi!
1️⃣ Grafici Ponderati
Nei grafici ponderati, ciascuna connessione ha un valore associato (chiamato peso). Questo valore viene usato per rappresentare una data relazione quantificabile tra i nodi che collega.
Per esempio i pesi potrebbero rappresentare distanza, tempo, il numero di connessioni condivise tra due utenti in un social network, o qualsiasi cosa che potrebbe essere usata per descrivere la connessione tra nodi nel contesto nel quale stai lavorando.
Questi pesi sono usati dall'algoritmo di Dijkstra per ottimizzare le rotte per trovare i percorsi più brevi o meno costosi tra i nodi in una rete.
2️⃣ Grafi Non Ponderati
Nei grafi non ponderati, al contrario, non abbiamo pesi associati alle loro connessioni. Un esempio di questo tipo di grafo si può trovare nei social network, dove le connessioni tra due utenti non possono essere quantificate. Pertanto la connessione non ha un peso.
💡 Nota: Potresti aver notato che, fino ad ora, i nostri grafi hanno solo una connessione che connette ciascuna coppia di nodi. È normale chiedersi se potrebbero esserci più connessioni tra una coppia di nodi. In effetti questo è possibile con i Multigrafi! Essi possono avere più connessioni che connettono la stessa coppia di nodi.
🏆 Numero di Connessioni! — Un Fattore Importante
È molto importante sapere se un grafo ha molte o poche connessioni in quanto questo è un fattore cruciale per decidere come vorrai rappresentare questa struttura dati nel tuo codice. Vediamo i diversi tipi! 👍
1️⃣ Grafo Denso
Sono i grafi che hanno molte connessioni. Ma, un momento! ⚠️ So quello che starai pensando, come puoi quantificare "molte connessioni"? Questo è piuttosto soggettivo, giusto? 😇 Sono d'accordo con te, quindi quantifichiamole:
👉 Troviamo il numero massimo di connessioni in un grafo orientato. Se ci sono |V| nodi in un grafo orientato (sei, nell'esempio qui sotto), vuol dire che ogni nodo può avere fino a |v| connessioni (nell'esempio qui sotto, sei).
Questo perché ogni nodo potrebbe potenzialmente essere connesso con tutti gli altri nodi e con sé stesso (vedi il "loop" qui sotto). Pertanto il numero massimo di connessioni che il grafo può avere è |V|*|V| , che rappresenta il numero totale di nodi moltiplicato per il numero massimo di connessioni che ogni nodo può avere.
Quando il numero di connessioni nel grafo è vicino al numero massimo di connessioni, il grafo è denso. 😉
💡 Nota: I “loop” si verificano quando un nodo ha una connessione che connette se stesso. Strano e interessante, vero? 😄
2️⃣ Grafi Sparsi
I grafi sparsi hanno poche connessioni. Come puoi vedere nel diagramma qui sotto, non ci sono molte connessioni tra i nodi.
Quando il numero di connessioni in un grafo è significativamente minore del numero massimo di connessioni, il grafo è sparso. 😉
⭕️ Ti Presento i Cicli!
Ora vediamo un concetto vitale per comprendere i grafi, i cicli.
Avrai probabilmente notato che, se segui una sequenza di connessioni in un grafo, potresti trovare il percorso che ti riporta allo stesso nodo. Questo è come "girare in tondo", esattamente come se stessi guidando per la tua città e prendessi un percorso che ti potrebbe portare al punto di partenza.
Nei grafi, questi percorsi "circolari" sono chiamati cicli. Sono percorsi validi che iniziano e finiscono allo stesso nodo. Per esempio, nel diagramma qui sotto, puoi vedere che partendo da qualsiasi nodo puoi ritornarci seguendo le connessioni.
I cicli non sono sempre "isolati" in quanto possono fare parte di un grafo più grande. Puoi rilevarli facendo partire la tua ricerca da uno specifico nodo e cercando un percorso che ti riporta allo stesso nodo.
👋 Riepilogando …
- I grafi sono strutture meravigliose che puoi usare quotidianamente tramite Google Search, Google Maps, GPS e i social media.
- Sono usati per rappresentare elementi che condividono connessioni.
- Gli elementi nel grafo sono chiamati nodi (nodes) i collegamenti tra loro connessioni (edges).
- I grafi possono essere orientati, quando le loro connessioni hanno uno specifico orientamento, simili alle strade a senso unico, oppure non orientati, quando le connessioni non hanno un orientamento specifico, simili alle strade a doppio senso.
- Le connessioni possono avere un valore associato ad esse, chiamato peso.
- Se un grafo ha molte connessioni si dice denso, altrimenti, se ha poche connessioni, viene detto sparso.
- Una serie di connessioni può formare un ciclo se esse creano un percorso che ti consente di tornare al nodo di partenza.
Continua ad apprendere queste stupende strutture! Ne varrà sicuramente la pena per il tuo futuro di programmatore. In questo momento sto imparando le strutture dati e le trovo assolutamente affascinanti. 😃 🎆 ❤️
La cosa importante è non smettere di fare domande. La curiosità esiste per ragioni proprie. — Albert Einstein
👋 Grazie!
Spero davvero che tu abbia apprezzato il mio articolo. ❤️
Seguimi su Twitter. 😃