Strutture Dati Avanzate
4.1 Alberi e Grafi
Alberi:
Struttura e Caratteristiche:
Gli alberi sono una struttura dati gerarchica costituita da nodi collegati in modo gerarchico.
Ogni albero ha un nodo speciale chiamato "radice" da cui si diramano i sotto-alberi.
Ogni nodo può avere zero o più nodi figlio, ad eccezione della radice, che non ha un nodo padre.
Alcune caratteristiche degli alberi includono altezza, profondità, foglie (nodi senza figli), nodi interni (nodi con almeno un figlio) e livello.
Alberi Binari e Alberi Binari di Ricerca (BST):
Gli Alberi Binari sono alberi in cui ogni nodo può avere al massimo due figli: sinistro e destro.
Gli Alberi Binari di Ricerca (BST) sono un tipo di albero binario dove ogni nodo ha un valore chiave e la chiave dei nodi nel sotto-albero sinistro è minore della chiave del nodo padre, mentre la chiave dei nodi nel sotto-albero destro è maggiore.
Applicazioni degli Alberi:
Gli alberi sono utilizzati in molteplici contesti come le strutture di dati (ad es. gli alberi AVL, alberi Red-Black), la rappresentazione di strutture gerarchiche (ad es. la gerarchia delle cartelle nei file system), e nell'informatica grafica per rappresentare gerarchie di oggetti.
Grafi:
Teoria dei Grafi:
I Grafi sono una collezione di nodi (o vertici) collegati da archi (o spigoli).
Possono essere diretti (orientati) o non diretti, a seconda che gli archi abbiano una direzione o meno.
Possono essere pesati o non pesati, dove i pesi possono rappresentare, ad esempio, la distanza tra due nodi.
Componenti dei Grafi:
Nodi/Vertici: Rappresentano entità o oggetti e possono avere attributi associati.
Archi/Spigoli: Definiscono le relazioni tra i nodi. Nei grafi diretti, gli archi hanno una direzione, mentre nei non diretti, sono bidirezionali.
Tipologie di Grafi:
Grafi Orientati (o Diretti): Gli archi hanno una direzione, quindi il percorso tra due nodi può essere diverso in base alla direzione degli archi.
Grafi Non Orientati: Gli archi non hanno direzione, e quindi il collegamento tra due nodi è bidirezionale.
Grafi Pesati: Gli archi hanno un peso associato che può rappresentare una distanza, un costo, o qualsiasi valore significativo.
Applicazioni dei Grafi:
I Grafi sono utilizzati per modellare relazioni tra entità (come le reti sociali), rappresentare circuiti, analizzare reti stradali, risolvere problemi di percorsi più brevi (come l'algoritmo di Dijkstra), tra molti altri utilizzi in varie discipline scientifiche e ingegneristiche.
4.2 Algoritmi su alberi
Visita in Profondità (DFS):
Funzionamento:
L'algoritmo DFS esplora un albero o un grafo andando il più in profondità possibile lungo un ramo prima di ritornare e continuare con altri rami.
Partendo da un nodo iniziale, visita uno dei suoi vicini non visitati e prosegue in profondità fino a quando non si è raggiunto il fondo del ramo.
Una volta raggiunto il fondo o trovato un nodo terminale, si torna indietro (backtracking) e si esplorano gli altri rami.
Implementazione:
L'implementazione dell'DFS può avvenire tramite ricorsione o utilizzando uno stack esplicito per tenere traccia dei nodi da visitare.
In un albero, l'DFS può essere implementato in modo ricorsivo, visitando il nodo corrente e poi chiamando se stessi sui nodi figli.
Applicazioni pratiche:
Trovare cammini in un grafo o in un albero.
Rilevare cicli in un grafo.
Ordinare i nodi di un grafo secondo il tempo di visita durante la DFS.
Visita in Ampiezza (BFS):
Funzionamento:
L'algoritmo BFS esplora un albero o un grafo iniziando dal nodo radice e visitando tutti i vicini del nodo corrente prima di procedere al livello successivo.
Esplora tutti i nodi a una profondità data prima di muoversi verso il livello successivo.
Utilizza una coda per mantenere traccia dei nodi da visitare, garantendo che i nodi adiacenti al nodo corrente siano visitati prima di passare ai nodi successivi.
Implementazione:
L'implementazione dell'BFS coinvolge l'utilizzo di una coda per memorizzare i nodi adiacenti da visitare.
In un albero, l'BFS può essere implementato utilizzando una coda e iterando attraverso i nodi livello per livello.
Applicazioni pratiche:
Trovare il percorso più breve tra due nodi in un grafo (algoritmo di Dijkstra utilizzando BFS per grafi non pesati).
Trovare tutti i nodi raggiungibili da un nodo in un grafo o in un albero.
Trovare cicli di lunghezza minima in un grafo non pesato.
Applicazioni Comuni di DFS e BFS:
Analisi di reti e grafi sociali.
Ricerca di percorsi o cammini tra due punti.
Analisi di alberi binari come alberi di ricerca binaria (BST).
4.3 Algoritmi su grafi
Algoritmo di Dijkstra:
Funzionamento:
L'algoritmo di Dijkstra è utilizzato per trovare il percorso più breve da un nodo di partenza a tutti gli altri nodi in un grafo pesato con archi non negativi.
Utilizza una coda di priorità (solitamente implementata con una coda min-heap) per selezionare il nodo successivo da esplorare in base alla distanza minima dal nodo di partenza.
Ad ogni iterazione, seleziona il nodo con la distanza minima, aggiorna le distanze dei suoi vicini se il percorso attraverso di essi è più breve e continua fino a quando tutti i nodi sono stati visitati.
Applicazioni:
Trovare il percorso più breve in una rete stradale, reti di telecomunicazione o in qualsiasi sistema che possa essere modellato come un grafo pesato.
Algoritmo di Bellman-Ford:
Funzionamento:
L'algoritmo di Bellman-Ford trova il percorso più breve da un nodo di partenza a tutti gli altri nodi in un grafo, anche in presenza di pesi negativi.
Utilizza un approccio di rilassamento degli archi per migliorare le stime delle distanze tra i nodi, iterando attraverso tutti gli archi e aggiornando le distanze se viene trovato un percorso più breve.
Può rilevare cicli di pesi negativi se esistono cicli la cui somma dei pesi è negativa.
Applicazioni:
È utilizzato quando ci sono archi con pesi negativi nel grafo o quando è necessario rilevare cicli di pesi negativi.
Algoritmi di Flusso Massimo:
Algoritmo di Ford-Fulkerson:
È un algoritmo generico per la risoluzione di problemi di flusso massimo in un grafo.
Utilizza la ricerca di cammini aumentanti da una sorgente a un pozzo per aumentare gradualmente il flusso fino a quando non è possibile aumentarlo ulteriormente.
Algoritmo di Edmonds-Karp:
È una variante dell'algoritmo di Ford-Fulkerson che utilizza la ricerca di cammini aumentanti con la BFS per migliorare le prestazioni in termini di tempo.
Applicazioni:
Risolvere problemi di flusso massimo, come l'ottimizzazione del flusso in una rete di trasporto o la massimizzazione del flusso di dati in una rete di computer.
Considerazioni generali:
Gli algoritmi di Dijkstra e Bellman-Ford sono utilizzati per trovare i percorsi più brevi in grafi con pesi, mentre gli algoritmi di flusso massimo sono applicati per ottimizzare il flusso in un grafo.
La scelta dell'algoritmo dipende dalle caratteristiche specifiche del grafo, come la presenza di pesi negativi, la necessità di trovare il percorso più breve o la massimizzazione del flusso.
Nessun commento:
Posta un commento