Non orientato
La relazione vale in entrambi i versi: {A, B} = {B, A}.
Algoritmi · Strutture dati
Grafi: visita in ampiezza e in profondità
Un grafo descrive chi è collegato a chi. BFS procede per livelli con una coda; DFS segue un cammino fino in fondo con uno stack. Nel laboratorio puoi vedere entrambe le strategie, un arco alla volta.
Che cos’è un grafo
Un grafo è una coppia G = (V, E): V è l’insieme dei vertici (o nodi), E quello degli archi che collegano coppie di vertici. È una struttura più generale di una lista o di un albero: può contenere cicli, più percorsi fra gli stessi nodi e componenti separate.
Orientato
L’arco è una coppia ordinata: A→B non implica B→A.
Pesato
Ogni arco ha un costo, una distanza o una capacità.
Disconnesso
Non esiste un cammino fra ogni coppia di vertici.
Modello prima dell’algoritmo. Una rete stradale può essere orientata, un’amicizia di solito no. La scelta cambia adiacenze, raggiungibilità e risultato della visita.
Vocabolario essenziale
Adiacenza e grado
Due vertici sono adiacenti se condividono un arco. Il grado conta gli archi incidenti; nei grafi orientati si distinguono grado entrante e uscente.
Cammino e distanza
Un cammino è una sequenza di vertici collegati. Nei grafi non pesati la distanza è il minimo numero di archi di un cammino.
Ciclo
È un cammino che torna al vertice iniziale. Per questo una visita deve ricordare i vertici già scoperti.
Componente
Una componente connessa è un insieme massimale di vertici reciprocamente raggiungibili. Da una sola sorgente si visita soltanto la sua componente.
Un albero è un grafo non orientato, connesso e aciclico. Ogni coppia di vertici ha un solo cammino semplice; con n vertici possiede esattamente n − 1 archi.
Come rappresentare un grafo
| Struttura | Memoria | Elencare i vicini di u | Verificare (u, v) | Quando conviene |
|---|---|---|---|---|
| Liste di adiacenza | Θ(|V| + |E|) | Θ(deg(u)) | O(deg(u)) | Grafi sparsi e visite BFS/DFS |
| Matrice di adiacenza | Θ(|V|²) | Θ(|V|) | Θ(1) | Grafi densi o query frequenti sugli archi |
| Lista degli archi | Θ(|E|) | Θ(|E|) | Θ(|E|) | Input, ordinamento o scansione globale degli archi |
A: [B, C]
B: [A, D]
C: [A, D]
D: [B, C] A B C D
A [ 0 1 1 0 ]
B [ 1 0 0 1 ]
C [ 1 0 0 1 ]
D [ 0 1 1 0 ]Nel laboratorio i vicini sono sempre esaminati in ordine alfabetico. Senza fissare un ordine, BFS e DFS restano corrette ma possono produrre alberi e sequenze differenti.
BFS vs DFS
| Aspetto | BFS · ampiezza | DFS · profondità |
|---|---|---|
| Frontiera | Coda FIFO | Stack LIFO o ricorsione |
| Strategia | Completa un livello prima del successivo | Segue un ramo e poi fa backtracking |
| Garantisce | Distanze minime in grafi non pesati | Tempi di scoperta/chiusura e struttura annidata |
| Usi tipici | Cammini minimi, livelli, bipartizione | Cicli, ordinamento topologico, componenti |
| Tempo | Θ(|V| + |E|) | Θ(|V| + |E|) |
| Spazio ausiliario | O(|V|) | O(|V|) |
Laboratorio: osserva la frontiera
Scegli un algoritmo e una sorgente, poi avanza arco per arco. Puoi fare clic su un nodo per renderlo sorgente, modificare gli archi o provare uno dei casi guidati.
Sintassi: A-B, A-C, F · da 2 a 10 vertici.
Esempi
non scopertoin frontieracorrenteconclusoarco dell’albero
Coda BFS · esce a sinistra
∅
Ordine di scoperta
—
Distanze dalla sorgente
Liste di adiacenza
- Vertici scoperti
- 0
- Archi esaminati
- 0
- Dimensione frontiera
- 0
- Alberi nella foresta
- 0
Perché funzionano e quanto costano
Invariante dei livelli
Quando un vertice u esce dalla coda, tutti i vertici a distanza minore sono già usciti e quelli appena scoperti hanno distanza d[u] + 1. La FIFO impedisce a un livello successivo di sorpassare quello corrente: la prima distanza assegnata è minima.
Invariante dello stack
Lo stack contiene sempre un cammino dalla radice al vertice corrente. Un vertice viene chiuso solo dopo aver esaminato tutti i suoi archi uscenti; i tempi di scoperta e fine producono intervalli annidati, utili per classificare la struttura del grafo.
Analisi della complessità con liste di adiacenza
- Ogni vertice viene scoperto una sola volta, inserito e rimosso dalla coda o dallo stack: Θ(|V|).
- Ogni lista di adiacenza viene scandita una sola volta. La somma delle lunghezze è |E| nei grafi orientati e 2|E| in quelli non orientati: Θ(|E|).
- Il totale è quindi Θ(|V| + |E|). Con una matrice di adiacenza occorre invece controllare un’intera riga per ogni vertice: Θ(|V|²).
- Colori, predecessori e distanze o tempi richiedono Θ(|V|); anche la frontiera può contenere Θ(|V|) vertici. Lo spazio ausiliario è Θ(|V|).
Attenzione alla ricorsione. Una DFS ricorsiva può usare Θ(|V|) frame e causare stack overflow su grafi molto profondi. La versione iterativa conserva la stessa complessità usando uno stack esplicito.
Quale visita scegliere
Cammino con meno archi · BFS
Salva il predecessore quando scopri un vertice, poi ricostruisci il cammino dalla destinazione alla sorgente.
Distanze e livelli · BFS
Gradi di separazione, propagazione a turni e test di bipartizione seguono naturalmente i livelli.
Dipendenze e cicli · DFS
Un arco verso un vertice ancora attivo rivela un ciclo orientato; l’ordine inverso di chiusura dà un ordinamento topologico se il grafo è aciclico.
Esplorazione e backtracking · DFS
Labirinti, componenti, ponti e punti di articolazione sfruttano la struttura profonda dell’albero DFS.
BFS non risolve il cammino minimo con pesi arbitrari: in quel caso servono, a seconda dei pesi, 0-1 BFS, Dijkstra o Bellman–Ford.
Errori comuni e domande per esercitarsi
- Segnare troppo tardi: un vertice va marcato come scoperto quando entra nella frontiera, non quando ne esce, altrimenti può essere inserito più volte.
- Dimenticare le componenti: una visita da s non prova che il grafo intero sia connesso. Per costruire una foresta, riparti da ogni vertice ancora bianco.
- Confondere DFS con “prendi un vicino qualsiasi”: DFS deve ricordare dove tornare; servono lo stack o i frame ricorsivi.
- Ignorare la rappresentazione: la formula Θ(|V| + |E|) presuppone liste di adiacenza, non una matrice.
Sul grafo ciclico, parti da A: prevedi ordine, distanze e predecessori BFS prima di avviare la simulazione.
Attiva il grafo disconnesso. Confronta il risultato con e senza “Tutte le componenti”: quanti alberi contiene la foresta?
Trova un grafo per cui BFS e DFS abbiano lo stesso ordine e uno per cui siano molto diverse. Che ruolo ha l’ordine dei vicini?