Teoria dei calcolatori e algoritmi: Algoritmi su grafi
Questa sezione esplora algoritmi fondamentali di grafi e ottimizzazione: dalle strategie di esplorazione come BFS e DFS, agli algoritmi di cammino minimo e di flusso massimo, fino alla costruzione di alberi di copertura e rilevamento di cicli. Una guida pratica per sviluppatori, ricercatori e studenti che vogliono comprendere le tecniche più efficaci, le loro applicazioni e le scelte strategiche nella risoluzione di problemi reali.
- Come funzionano BFS e DFS e quando si usa ciascuno?
- Come si implementa l'algoritmo di Dijkstra per il cammino minimo?
- Qual è la differenza tra Prim e Kruskal per il minimum spanning tree?
- Come si rilevano cicli in un grafo diretto e non-diretto?
- Come funziona l'algoritmo di Ford-Fulkerson per il flusso massimo?
Come funzionano BFS e DFS e quando si usa ciascuno?
BFS (Breadth-First Search): Esplora il grafo livello per livello usando una coda, visitando prima tutti i nodi adiacenti alla radice, poi i loro vicini non visitati, e così via. Garantisce di trovare il cammino
più breve (in numero di archi) tra due nodi in grafi non pesati. Complessità: O(V + E).
Applicazioni di BFS:
Cammini minimi in grafi non pesati
Livelli di connettività e componenti connesse
Alberi di copertura (spanning tree) con profondità minima
Web crawling per scoperta di pagine vicine
Ricerca di percorsi in labirinti e giochi
Applicazioni di DFS:
Rilevamento di cicli in grafi diretti e non-diretti
Ordinamento topologico (topological sort)
Componenti fortemente connesse (Kosaraju, Tarjan)
Punti di articolazione e bridge detection
Backtracking e generazione di soluzioni complete
Classificazione degli archi (tree, back, forward, cross edges)
Come si implementa l'algoritmo di Dijkstra per il cammino minimo?
L'algoritmo di Dijkstra calcola i cammini minimi da un nodo sorgente s a tutti gli altri nodi in un grafo con pesi non-negativi. Utilizza una strategia greedy basata su rilassamento progressivo.
Implementazione:
- Inizializzazione: dist[s] = 0, dist[v] = ∞ per tutti gli altri nodi; prev[v] = null per ricostruzione del percorso
- Priority Queue: Inserisci tutti i nodi nella priority queue ordinata per distanza minima
- Rilassamento: Estrai il nodo u con distanza minima; per ogni vicino v di u, se dist[u] + peso(u,v) < dist[v], aggiorna dist[v] e prev[v]
- Iterazione: Ripeti fino a coda vuota o tutti i nodi visitati
Ottimizzazioni pratiche:
Early termination: fermarsi quando si raggiunge il nodo destinazione
Bidirectional search: ricerca simultanea da sorgente e destinazione
A* extension: aggiungere euristica h(n) per ricerca guidata
Qual è la differenza tra Prim e Kruskal per il minimum spanning tree?
Entrambi costruiscono il minimum spanning tree (MST) di un grafo connesso non-diretto, ma con approcci diversi:
Algoritmo di Prim:
Approccio: Cresce l'albero un vertice alla volta, partendo da un nodo arbitrario
Strategia: Ad ogni passo, aggiunge l'arco di peso minimo che connette un nodo già nell'albero a uno esterno
Implementazione: Priority queue per archi candidati, array per tracciare nodi nell'albero
Complessità: O(E log V) con binary heap, O(E + V log V) con Fibonacci heap
Efficiente per: Grafi densi (E ≈ V²) dove la gestione di tutti gli archi è costosa
Approccio: Considera tutti gli archi ordinati per peso crescente
Strategia: Aggiunge archi se non creano cicli, utilizzando Union-Find per rilevazione cicli
Implementazione: Ordinamento iniziale O(E log E), poi Union-Find per ogni arco
Complessità: O(E log E) dominato dall'ordinamento, O(E α(V)) per Union-Find
Efficiente per: Grafi sparsi (E ≈ V) dove ordinare gli archi non è proibitivo
Come si rilevano cicli in un grafo diretto e non-diretto?
La rilevazione di cicli dipende dal tipo di grafo e richiede strategie diverse:
Grafo non-diretto:
DFS con parent tracking: Durante DFS, se si incontra un nodo già visitato che non è il parent del nodo corrente, esiste un ciclo
Union-Find: Per ogni arco (u,v), se u e v sono già nella stessa componente connessa, l'aggiunta dell'arco crea un ciclo
Complessità: O(V + E) per DFS, O(E α(V)) per Union-Find
DFS con colori: Tre stati per nodo: bianco (non visitato), grigio (in ricorsione), nero (completato). Ciclo se si raggiunge un nodo grigio
Topological sort: Se impossibile ordinare tutti i nodi topologicamente, il grafo ha cicli
Kahn's algorithm: Rimuovi iterativamente nodi con in-degree 0; se rimangono nodi non processati, ci sono cicli
Floyd's cycle detection: Per grafi funzionali (ogni nodo ha esattamente un arco uscente)
Johnson's algorithm: Enumerazione di tutti i cicli semplici
Strongly Connected Components: Kosaraju o Tarjan per identificare cicli in componenti fortemente connesse
Come funziona l'algoritmo di Ford-Fulkerson per il flusso massimo?
Ford-Fulkerson è una famiglia di algoritmi per trovare il flusso massimo in una rete di flusso da una sorgente s a un pozzo t.
Concetti chiave:
Capacità residua: c_f(u,v) = c(u,v) - f(u,v) per arco diretto, f(v,u) per arco inverso
Grafo residuo: G_f contiene archi con capacità residua > 0
Percorso aumentante: cammino da s a t nel grafo residuo
Taglio: partizione (S,T) con s ∈ S, t ∈ T; max-flow = min-cut per teorema di dualità
- Inizializzazione: f(u,v) = 0 per tutti gli archi
- Ricerca percorso aumentante: BFS o DFS nel grafo residuo da s a t
- Calcolo bottleneck: capacità residua minima lungo il percorso
- Aggiornamento flusso: aumenta flusso di bottleneck lungo il percorso, diminuisci sul percorso inverso
- Iterazione: ripeti finché non esistono percorsi aumentanti
Edmonds-Karp: usa BFS per percorsi aumentanti, O(VE²)
Dinic: costruisce grafo dei livelli, O(V²E)
Push-Relabel: approccio locale invece di percorsi globali, O(V²E) con euristiche gap e global relabeling
Faq
In che modo BFS e DFS differiscono nella gestione dei nodi?
BFS esplora i nodi livello per livello utilizzando una coda, mentre DFS segue un ramo fino in fondo usando stack o ricorsione, esplorando prima i percorsi profondi.
Quando è preferibile usare BFS rispetto a DFS?
BFS è preferibile per trovare cammini minimi in grafi non pesati e per esplorazioni livello per livello, mentre DFS è utile per analisi strutturale, rilevamento di cicli e backtracking.
Qual è il principio base dell’algoritmo di Dijkstra?
Dijkstra utilizza una strategia greedy basata sul rilassamento progressivo dei nodi, calcolando distanze minime da un nodo sorgente a tutti gli altri nodi in grafi con pesi non negativi.
Quali strutture dati sono essenziali per Dijkstra?
Una priority queue per estrarre il nodo con distanza minima e array o mappe per tracciare le distanze e i predecessori dei nodi lungo i cammini minimi.
Quali differenze ci sono tra Prim e Kruskal per il MST?
Prim cresce l’albero aggiungendo nodi tramite archi minimi connessi all’albero corrente, ideale per grafi densi. Kruskal ordina tutti gli archi e li aggiunge evitando cicli, adatto a grafi sparsi.
Come rilevare cicli in un grafo non-diretto?
Si può usare DFS con parent tracking o Union-Find: se un nodo visitato non è il parent corrente, o se due nodi dell’arco appartengono già alla stessa componente, esiste un ciclo.
Come rilevare cicli in un grafo diretto?
DFS con colori dei nodi (bianco, grigio, nero) permette di identificare cicli; altri metodi includono ordinamento topologico e l’algoritmo di Kahn.
Quali concetti chiave sono alla base di Ford-Fulkerson?
Capacità residua, grafo residuo, percorsi aumentanti e il teorema max-flow = min-cut. L’algoritmo aumenta iterativamente il flusso lungo i percorsi residui fino a saturazione.
Quali varianti implementative esistono per il flusso massimo?
Edmonds-Karp (BFS), Dinic (grafo dei livelli), Push-Relabel (approccio locale), ciascuna con complessità e ottimizzazioni diverse per grafi di dimensioni variabili.
Quali sono le applicazioni pratiche dei principali algoritmi di grafo?
Cammini minimi, alberi di copertura, rilevamento cicli, analisi di flusso massimo, web crawling, labirinti e giochi, matching bipartito, min-cut e segmentazione di immagini.
