Grafi e ricerca di percorsi — Informatica, 14–17 anni
Un grafo rappresenta elementi e collegamenti tra loro. Quando un problema viene disegnato in questo modo, un computer può esplorare percorsi, connessioni o dipendenze invece di trattare ogni situazione come un caso a parte.
Elementi e collegamenti
In un grafo, un vertice rappresenta una cosa e un arco rappresenta una relazione o un percorso tra le cose. Le città possono essere vertici e le strade archi; le persone possono essere vertici e le amicizie archi. Gli archi possono avere direzione o peso, come un senso unico o una distanza in chilometri.
Perché disegnare un grafo?
Molti problemi reali riguardano collegamenti: consegnare pacchi, instradare messaggi, suggerire amici o ordinare compiti con prerequisiti. Liste di fatti isolati nascondono questi legami. I grafi offrono al computer una forma comune, utile per strade, siti web o dipendenze.
Scegliere il percorso più breve
Supponiamo che A sia collegato a B in 4 km, ad C in 1 km, C a B in 2 km e B a D in 3 km. Da A a B, il percorso diretto è di 4 km, ma A–C–B è 1 + 2 = 3 km, quindi è più breve. Da A a D passando per C e B, il totale è 1 + 2 + 3 = 6 km.
Meno passaggi non significa percorso più breve
È naturale contare solo quanti collegamenti usa un percorso: due strade sembrano meglio di tre. Ma i collegamenti possono avere lunghezze, ritardi o prezzi molto diversi. Un percorso con tre archi da 1 km può essere migliore di uno con due archi da 10 km, quindi il grafo deve registrare ciò che conta davvero.
Grafi fuori dalla scuola
Le app di navigazione usano grafi stradali con distanze e tempi di traffico. Le piattaforme social usano grafi di account e relazioni, mentre un motore di ricerca può seguire collegamenti tra pagine. In ogni caso il risultato dipende da cosa è un collegamento e da quale peso conta: distanza, tempo, costo o rilevanza.
Continua a esplorare
Altre lingue
Caricamento di MyLeoNes™…