Come visitare un grafo e trovare cammini di peso minimo
Gli alberi permettono di rappresentare solo relazioni strettamente gerarchiche (dove ogni nodo ha un unico padre e non esistono cicli). Quando dobbiamo modellare relazioni arbitrarie tra coppie di oggetti — come una rete stradale di città, la topologia dei router di Internet, le amicizie in un social network, o le dipendenze tra pacchetti software — utilizziamo la struttura matematica e informatica più generale: il Grafo.
Definizione formale e terminologia dei Grafi
Un Grafo è una coppia ordinata G=(V,E) dove:
V è un insieme finito e non vuoto di elementi chiamati vertici (o nodi); indichiamo il numero di vertici con ∣V∣=n.
E è un insieme di coppie di vertici chiamate archi (o spigoli / lati, edges); indichiamo il numero di archi con ∣E∣=m.
Classificazione dei grafi
Grafo Non Orientato (Undirected Graph):
Gli archi sono coppie non ordinate{u,v}: la connessione è bidirezionale/simmetrica ((u,v) equivale a (v,u), come l’amicizia reciproca o una strada a doppio senso). Il numero massimo di archi (senza cappi) è (2∣V∣)=2∣V∣(∣V∣−1)=Θ(∣V∣2).
Grafo Orientato o Digrafo (Directed Graph):
Gli archi sono coppie ordinate(u,v) rappresentate da frecce u→v, dove u è la coda/sorgente e v è la testa/destinazione (come i link tra pagine web o il “seguire” su un social). Il numero massimo di archi è ∣V∣(∣V∣−1)=Θ(∣V∣2).
Grafo Pesato (Weighted Graph):
Ad ogni arco e=(u,v)∈E è associato un numero reale w(u,v) chiamato peso o costo (es. distanza in km, latenza in ms, costo del pedaggio).
flowchart LR
subgraph NonOrientato["Grafo Non Orientato"]
U0((0)) --- U1((1))
U0 --- U2((2))
U1 --- U2
U2 --- U3((3))
end
subgraph OrientatoPesato["Grafo Orientato e Pesato (Digrafo)"]
D0((0)) -->|"peso 4"| D1((1))
D0 -->|"peso 2"| D2((2))
D2 -->|"peso 1"| D1
D1 -->|"peso 5"| D3((3))
end
Grado, Cammini, Cicli, Connessione e Alberi
Adiacenza e Grado: Se (u,v)∈E, il vertice v si dice adiacente a u.
In un grafo non orientato, il grado deg(u) è il numero di archi incidenti in u. Vale il Lemma delle strette di mano: ∑u∈Vdeg(u)=2∣E∣.
In un grafo orientato, si distinguono il grado entrante (in-degree) (numero di frecce che arrivano in u) e il grado uscente (out-degree) (numero di frecce che partono da u). Vale ∑uout-deg(u)=∑uin-deg(u)=∣E∣.
Cammino (Path): Una sequenza di vertici ⟨v0,v1,…,vk⟩ collegati da archi consecutivi (vi−1,vi)∈E. La lunghezza del cammino è il numero di archi k (o la somma dei pesi in un grafo pesato). Un cammino è semplice se non ripete vertici.
Ciclo (Cycle): Un cammino di lunghezza ≥1 in cui il vertice finale coincide con quello iniziale (v0=vk). Un grafo privo di cicli si dice aciclico. Un grafo orientato aciclico è chiamato DAG (Directed Acyclic Graph).
Connessione e Alberi Liberi: Un grafo non orientato è connesso se esiste almeno un cammino tra qualsiasi coppia di vertici. Un Albero è semplicemente un grafo non orientato connesso e aciclico, ed è caratterizzato dalla relazione fondamentale:
∣E∣=∣V∣−1
Grafo Sparso vs Grafo Denso: Un grafo si dice sparso se ∣E∣≪∣V∣2 (es. ∣E∣=O(∣V∣), come le reti stradali dove ogni incrocio ha 3–4 strade); si dice denso se ∣E∣≈Θ(∣V∣2).
Rappresentazione dei Grafi in memoria in C
Supponendo di numerare i vertici da 0 a V−1, esistono due strutture dati canoniche per rappresentare un grafo:
1. Matrice di Adiacenza (Adjacency Matrix)
È una matrice quadrata A di dimensione ∣V∣×∣V∣ in cui:
(Nota: se il grafo non è orientato, la matrice di adiacenza è simmetrica: A[u][v]=A[v][u]).
2. Liste di Adiacenza (Adjacency Lists)
È un array di ∣V∣ puntatori a liste concatenate, dove la lista adj[u] contiene esclusivamente i vertici v adiacenti a u (cioè gli archi uscenti da u).
flowchart LR
subgraph AdjList["Rappresentazione con Liste di Adiacenza"]
A0["adj[0]"] --> L01["1 | ●"] --> L02["2 | NULL"]
A1["adj[1]"] --> L13["3 | NULL"]
A2["adj[2]"] --> L21["1 | ●"] --> L23["3 | NULL"]
A3["adj[3]"] --> L3N["NULL"]
end
Tabella comparativa: Matrice vs Liste di Adiacenza
Criterio / Operazione
Matrice di Adiacenza
Liste di Adiacenza
Spazio di memoria S(V,E)
**$\Theta(
V
Testare se esiste l’arco (u,v)
Θ(1) (basta leggere A[u][v])
O(deg(u)) (bisogna scorrere la lista adj[u])
Scorrere tutti i vicini di u
**$\Theta(
V
Inserire un arco (u,v)
Θ(1)
Θ(1) (inserimento in testa a adj[u])
Quando conviene usarla?
Grafi DENSI ($
E
Algoritmi di Visita e Ricerca sui Grafi
Per esplorare tutti i vertici raggiungibili da un vertice sorgente s senza cadere in cicli infiniti, manteniamo un array booleano visitato[V] (inizializzato a 0). Esistono due strategie universali di esplorazione, entrambe di complessità ottima Θ(∣V∣+∣E∣) con liste di adiacenza (e Θ(∣V∣2) con matrice di adiacenza):
1. Ricerca in Ampiezza: BFS (Breadth-First Search)
La BFS esplora il grafo “a onde concentriche” (per livelli di distanza dalla sorgente s): prima visita s (distanza 0), poi tutti i vicini a distanza 1, poi tutti i vertici a distanza 2, e così via.
Struttura dati di supporto: utilizza una Coda FIFO (Queue).
Proprietà fondamentale: In ogni grafo non pesato, la BFS calcola la distanza minima dist[v] (cammino minimo col minor numero di archi) dalla sorgente s a tutti gli altri vertici, costruendo l’albero dei cammini minimi tramite il vettore dei padri padre[v]!
2. Ricerca in Profondità: DFS (Depth-First Search)
La DFS esplora il grafo spingendosi il più lontano possibile lungo un singolo cammino finché non incontra un vicolo cieco (tutti i vicini già visitati), per poi fare backtracking all’ultimo bivio non ancora esaurito.
Struttura dati di supporto: utilizza la ricorsione (lo Stack delle chiamate) oppure una Pila LIFO (Stack) esplicita.
Applicazioni: Individuazione di cicli, calcolo delle componenti connesse, ordinamento topologico di un DAG, risoluzione di labirinti.
Cenni all’Algoritmo di Dijkstra per Grafi Pesati (w(u,v)≥0)
Quando gli archi hanno pesi positivi diversi tra loro, il cammino con meno archi (trovato dalla BFS) non è necessariamente il cammino di peso totale minimo!
L’Algoritmo di Dijkstra generalizza la BFS sostituendo la Coda FIFO con una Coda con Priorità (Min-Heap):
Inizializza dist[s] = 0 e dist[v] = +INFINITO per tutti gli altri vertici;
Ad ogni passo estrae il vertice non ancora definitivo u avente dist[u] minima;
Rilassa (Relaxation) tutti gli archi uscenti (u,v): se passare per u migliora la distanza verso v, aggiorna:
se dist[u]+w(u,v)<dist[v]⟹dist[v]=dist[u]+w(u,v),padre[v]=u
Implementazione completa in C: Grafo con Liste di Adiacenza, BFS e DFS
#include <stdio.h>#include <stdlib.h>/* Nodo di una lista di adiacenza */typedef struct ArcoNodo { int dest; struct ArcoNodo *next;} ArcoNodo;/* Struttura del Grafo con Liste di Adiacenza */typedef struct { int V; /* Numero di vertici (0 .. V-1) */ ArcoNodo **adj; /* Array di V puntatori alle liste di adiacenza */} Grafo;Grafo *grafo_crea(int V) { Grafo *g = (Grafo *)malloc(sizeof(Grafo)); if (!g) return NULL; g->V = V; g->adj = (ArcoNodo **)calloc(V, sizeof(ArcoNodo *)); if (!g->adj) { free(g); return NULL; } return g;}/* Aggiunge un arco orientato u -> v in tempo O(1) */void grafo_aggiungi_arco(Grafo *g, int u, int v) { ArcoNodo *nuovo = (ArcoNodo *)malloc(sizeof(ArcoNodo)); if (!nuovo) return; nuovo->dest = v; nuovo->next = g->adj[u]; g->adj[u] = nuovo;}/* === 1. VISITA IN AMPIEZZA (BFS) con calcolo delle distanze minime === */void grafo_bfs(const Grafo *g, int sorgente) { int *visitato = (int *)calloc(g->V, sizeof(int)); int *dist = (int *)malloc(g->V * sizeof(int)); int *coda = (int *)malloc(g->V * sizeof(int)); int head = 0, tail = 0; for (int i = 0; i < g->V; i++) dist[i] = -1; /* Inizializza la BFS dalla sorgente */ visitato[sorgente] = 1; dist[sorgente] = 0; coda[tail++] = sorgente; /* enqueue(sorgente) */ printf("Ordine BFS da %d: ", sorgente); while (head < tail) { int u = coda[head++]; /* dequeue() */ printf("%d(d=%d) ", u, dist[u]); /* Esplora tutti i vicini v di u */ for (ArcoNodo *p = g->adj[u]; p != NULL; p = p->next) { int v = p->dest; if (!visitato[v]) { visitato[v] = 1; dist[v] = dist[u] + 1; coda[tail++] = v; /* enqueue(v) */ } } } printf("\n"); free(visitato); free(dist); free(coda);}/* === 2. VISITA IN PROFONDITA (DFS) ricorsiva === */static void dfs_ric(const Grafo *g, int u, int visitato[]) { visitato[u] = 1; printf("%d ", u); for (ArcoNodo *p = g->adj[u]; p != NULL; p = p->next) { int v = p->dest; if (!visitato[v]) { dfs_ric(g, v, visitato); } }}void grafo_dfs(const Grafo *g, int sorgente) { int *visitato = (int *)calloc(g->V, sizeof(int)); printf("Ordine DFS da %d: ", sorgente); dfs_ric(g, sorgente, visitato); printf("\n"); free(visitato);}void grafo_distruggi(Grafo *g) { if (!g) return; for (int i = 0; i < g->V; i++) { ArcoNodo *curr = g->adj[i]; while (curr) { ArcoNodo *succ = curr->next; free(curr); curr = succ; } } free(g->adj); free(g);}
Cammini minimi con Dijkstra e Bellman–Ford
Il rilassamento di un arco orientato u → v di peso w aggiorna d[v] e il predecessore se d[u] è finita e d[u] + w < d[v]. Con rappresentazioni intere, teniamo lo stato irraggiungibile separato e verifichiamo che la somma sia rappresentabile prima di calcolarla. La lista di adiacenza permette di visitare solo gli archi uscenti.
Dijkstra con pesi non negativi
Consideriamo S → A (4), S → B (1), B → A (2), A → T (1) e B → T (6). Estraendo S si ottengono d[A]=4 e d[B]=1. Estraendo B si aggiornano d[A]=3 e d[T]=7. Estraendo A si migliora d[T] a 4, quindi si estrae T. Seguendo i predecessori otteniamo S → B → A → T. La distanza minima temporanea diventa definitiva all’estrazione: proseguire da un altro vertice ancora da elaborare non può ridurla con archi di peso non negativo. Ci fermiamo quando il prossimo minimo è infinito o non ci sono candidati. Con selezione del minimo per scansione e matrice, il tempo è O(V2). Con liste e min-heap indicizzato è O((V+E)logV) per V≥2.
Bellman–Ford e cicli negativi
Bellman–Ford scorre tutti gli archi per al più V−1 passate, rilassando solo quelli con coda raggiungibile. Si può terminare presto se nessun valore cambia. Senza cicli negativi raggiungibili, un cammino minimo può essere scelto semplice e usa al più V−1 archi. Dopo k passate sono state considerate almeno tutte le possibilità con al più k archi. Il costo con una lista di archi è O(V+VE) e la memoria ausiliaria è O(V).
Esempio. In ogni passata consideriamo gli archi nell’ordine A → T (2), B → A (-3), S → B (5) e S → A (4).
Passata
d[S]
d[A]
d[B]
d[T]
0
0
∞
∞
∞
1
0
4
5
∞
2
0
2
5
6
3
0
2
5
4
La distanza di T è 4 via S → B → A → T. Per rilevare cicli negativi raggiungibili, dopo le V−1 passate controlliamo se un altro rilassamento può migliorare una distanza. Aggiungendo A → B (2), il ciclo B → A → B pesa −1 ed è raggiungibile da S. Una passata ulteriore trova ancora un miglioramento. I vertici raggiungibili da quel ciclo non hanno distanza minima finita. Un ciclo che la sorgente non raggiunge non influenza le sue distanze.
Esempi guidati
Esempio 1: Traccia passo-passo di BFS e DFS su un grafo concreto
Dato il grafo non orientato con V={0,1,2,3,4,5} e liste di adiacenza (ordinate in senso crescente):
adj[0] = {1, 2}
adj[1] = {0, 3, 4}
adj[2] = {0, 4}
adj[3] = {1, 5}
adj[4] = {1, 2, 5}
adj[5] = {3, 4}
Traccia della BFS partendo da 0:
Livello d=0: Coda [0]→ estrae 0, scopre e accoda i vicini 1 (d=1) e 2 (d=1). Coda: [1, 2].
Livello d=1:
Estrae 1, scopre e accoda 3 (d=2) e 4 (d=2). Coda: [2, 3, 4].
Estrae 2, i suoi vicini 0 e 4 sono già visitati! Coda: [3, 4].
Livello d=2:
Estrae 3, scopre e accoda 5 (d=3). Coda: [4, 5].
Estrae 4, i suoi vicini 1, 2, 5 sono già visitati! Coda: [5].
Livello d=3: Estrae 5. Coda vuota.
Sequenza BFS: 0, 1, 2, 3, 4, 5.
Traccia della DFS ricorsiva partendo da 0:
Visita 0→ scende nel primo vicino non visitato 1→ scende nel primo vicino 3→ scende in 5→ scende in 4→ scende in 2. Da 2 tutti i vicini (0 e 4) sono già visitati, quindi risale fino a 0.
Sequenza DFS: 0, 1, 3, 5, 4, 2.
Esempio 2: Contare il numero di Componenti Connesse di un grafo non orientato
Se un grafo non è connesso, è formato da più “isole” disgiunte chiamate componenti connesse. Per contarle in tempo Θ(∣V∣+∣E∣), basta eseguire un ciclo su tutti i vertici v∈V: ogni volta che troviamo un vertice non ancora visitato, incrementiamo il contatore delle isole e lanciamo una DFS/BFS da v che marcherà tutta la sua isola!
int conta_componenti_connesse(const Grafo *g) { int *visitato = (int *)calloc(g->V, sizeof(int)); int num_componenti = 0; for (int v = 0; v < g->V; v++) { if (!visitato[v]) { num_componenti++; /* Trovata una nuova componente connessa! */ dfs_ric(g, v, visitato); /* Marca tutti i vertici raggiungibili da v */ } } free(visitato); return num_componenti;}
Errori frequenti
Errori da evitare
Dimenticare l’array visitato[] durante la visita di un grafo:
A differenza degli alberi (che non hanno cicli), i grafi possono contenere cicli (o archi bidirezionali u↔v). Senza il vettore visitato[], sia la BFS sia la DFS rimbalzano all’infinito tra u e v fino al crash!
Nella BFS, marcare visitato[v] = 1 solo quando v viene estratto dalla coda (dequeue) anziché quando viene inserito (enqueue):
Se si marca un vertice come visitato solo al momento della dequeue, lo stesso vertice v può essere accodato più volte da più vicini diversi prima di essere estratto, gonfiando la coda e rallentando l’algoritmo. Regola d’oro: visitato[v] = 1 va impostato subito prima di enqueue(v)!
Applicare l’algoritmo di Dijkstra a grafi con archi di peso negativo:
Dijkstra assume che aggiungere un arco a un cammino non possa mai diminuirne il peso totale (w(u,v)≥0). Con pesi negativi, rendere definitiva la distanza all’estrazione può dare un risultato errato. Bellman–Ford tratta anche questi archi.
Esercizi di prova
Esercizio 1. Scelta tra Matrice e Liste di Adiacenza (Base)
Un grafo orientato rappresenta una rete stradale con ∣V∣=100000 incroci e ∣E∣=300000 tratti stradali. Calcola l’ordine di grandezza della memoria richiesta dalla Matrice di Adiacenza (assumendo 1 byte per cella) rispetto alle Liste di Adiacenza, e stabilisci quale rappresentazione è necessaria.
Soluzione
Matrice di Adiacenza: richiede ∣V∣2=(105)2=1010 celle ≈10 GB di RAM, quasi tutta piena di zeri (il grafo è estremamente sparso: solo lo 0.003% delle coppie ha un arco!).
Liste di Adiacenza: richiedono un vettore di 100000 puntatori più 300000 nodi lista (Θ(∣V∣+∣E∣)), occupando appena pochi Megabyte (≈5.6 MB)!
Per grafi sparsi di grandi dimensioni le Liste di Adiacenza sono l’unica scelta praticabile.
Esercizio 2. Calcolo di grado entrante e uscente su Matrice di Adiacenza (Base)
Dato un grafo orientato rappresentato tramite una matrice di adiacenza int A[V][V], scrivi due funzioni int grado_uscente(int A[V][V], int u) e int grado_entrante(int A[V][V], int u) e indicane la complessità temporale.
Soluzione
/* Il grado uscente di u è la somma della RIGA u: costo Theta(V) */int grado_uscente(int V, int A[V][V], int u) { int deg = 0; for (int v = 0; v < V; v++) { if (A[u][v] != 0) deg++; } return deg;}/* Il grado entrante di u è la somma della COLONNA u: costo Theta(V) */int grado_entrante(int V, int A[V][V], int u) { int deg = 0; for (int v = 0; v < V; v++) { if (A[v][u] != 0) deg++; } return deg;}
Esercizio 3. Verifica di grafo non orientato tramite simmetria (Intermedio)
Scrivi una funzione int matrice_simmetrica(int V, int A[V][V]) che verifica se la matrice di adiacenza A rappresenta un grafo non orientato privo di cappi (A[u][u]==0 e A[u][v]==A[v][u]) ispezionando solo il triangolo superiore della matrice.
Soluzione
int matrice_simmetrica(int V, int A[V][V]) { for (int i = 0; i < V; i++) { if (A[i][i] != 0) return 0; /* Presenza di un cappio (self-loop) */ for (int j = i + 1; j < V; j++) { if (A[i][j] != A[j][i]) { return 0; /* Arco non simmetrico */ } } } return 1;}
Esercizio 4. Ricostruzione del cammino minimo dopo la BFS (Intermedio)
Supponi che la BFS a partire da sorgente abbia popolato il vettore dei padri int padre[V] (dove padre[sorgente] = -1 e padre[v] = u indica che v è stato scoperto da u). Scrivi una procedura ricorsiva void stampa_cammino(const int padre[], int s, int dest) che stampa i vertici del cammino minimo da s a dest nell’ordine corretto da s a dest.
Soluzione
void stampa_cammino(const int padre[], int s, int dest) { if (dest == s) { printf("%d", s); return; } if (padre[dest] == -1) { printf("Nessun cammino da %d a %d", s, dest); return; } stampa_cammino(padre, s, padre[dest]); printf(" -> %d", dest);}
Esercizio 5. Test se un grafo non orientato è un Albero (Avanzato)
Ricordando che un grafo non orientato G=(V,E) è un albero se e solo se è connesso e ha esattamente ∣E∣=∣V∣−1 archi, spiega come verificare in tempo Θ(∣V∣+∣E∣) se un grafo non orientato rappresentato con liste di adiacenza è un albero.
Soluzione
Conteggio degli archi: Scorriamo tutte le liste di adiacenza sommando le loro lunghezze per ottenere ∑deg(u)=2∣E∣. Se ∣E∣=∣V∣−1, possiamo restituire subito false!
Verifica della connessione: Lanciamo una singola visita DFS (o BFS) a partire dal vertice 0 e contiamo quanti vertici vengono visitati. Se tutti i ∣V∣ vertici risultano visitati (e avevamo già verificato ∣E∣=∣V∣−1), un teorema fondamentale della teoria dei grafi garantisce che il grafo è sia connesso sia aciclico, quindi è un albero (true).
Esercizio 6. Traccia dell’Algoritmo di Dijkstra (Avanzato)
Dato un grafo orientato pesato con vertici {0,1,2,3} e archi: 0→1 (peso 6), 0→2 (peso 2), 2→1 (peso 3), 1→3 (peso 1), 2→3 (peso 5),
calcola passo dopo passo il vettore delle distanze minime dist[] dalla sorgente 0 applicando l’algoritmo di Dijkstra.
Soluzione
Inizializzazione: dist = [0, +∞, +∞, +∞], insieme dei definitivi S=∅.
Passo 1: Estraiamo il minimo u = 0 (dist[0] = 0). Rilassiamo gli archi da 0:
Passo 4: Estraiamo u = 3 (dist[3] = 6). Fine! Distanze minime finali da 0: dist = [0, 5, 2, 6] (il cammino minimo da 0 a 3 è 0→2→1→3 di costo 2+3+1=6).
Provenienza del materiale
Dispensa ufficiale del corso: C1PROG1U6L4_Ricerca_Applicata_ai_Grafi.pdf (Unità 6, Lezione 4 — Ricerca applicata ai grafi).
Marco Anisetti, Algoritmi e strutture dati dinamiche, C1PROG1_Appunti_di_fine_unità_6.pdf, capp. 2 e 4.