Tutorato per Immatricolati a.a.
2025/26
Roberto Grossi
16 aprile 2026
1 Rappresentazione dei grafi
Un grafo con N nodi numerati da 0 a N − 1 può essere rappresentato in diversi modi. Le due rappresentazioni
fondamentali sono la matrice di adiacenza e la lista di adiacenza.
La matrice di adiacenza è una matrice quadrata N ×N in cui l’elemento in posizione (i, j) indica la presenza o assenza
dell’arco da i a j. Nel caso di grafi orientati, la matrice non è necessariamente simmetrica. Questa rappresentazione è
semplice e permette di verificare rapidamente l’esistenza di un arco, ma richiede spazio proporzionale a N 2 .
La lista di adiacenza rappresenta invece, per ogni nodo u, l’insieme dei nodi adiacenti a u. Questa struttura è
particolarmente efficiente per grafi sparsi, perché utilizza spazio proporzionale a N + M , dove M è il numero di archi.
Nel codice JavaScript seguente si utilizza una lista di adiacenza:
let adj = [];
function leggiGrafoOrientato(numNodes, edges) {
adj = [Link]({ length: numNodes }, () => []);
for (const [u, v] of edges)
adj[u].push(v);
}
In questo modo, per ogni nodo u, l’array adj[u] contiene tutti i nodi v tali che esiste un arco (u, v).
grado
2 0 1 | 6 const edges = [
[0, 1],
3 1 [0, 6],
3 2 3 | 1 [6, 7],
[7, 2],
2 3 [2, 3],
3 4 3 [7, 4],
[6, 5],
2 5 4 | 6 [2, 1],
[7, 1],
3 6 7 | 5
[7, 3],
4 7 2 | 4 | 1 | 3 [4, 3],
Text [5, 4],
0 [5, 6]
2 3
];
'0'
1 6
'1'
'6'
1 7 4
7 5 '7'
'2'
2 4 '3'
'4' 0 6 5
'5'
3
2 Visita DFS
La visita DFS (Depth-First Search) esplora il grafo seguendo un cammino il più in profondità possibile prima di tornare
indietro. L’idea è quella di visitare ricorsivamente i nodi non ancora visitati.
Nel codice fornito, la DFS è implementata come segue:
function DFS(u) {
1
visitato[u] = true;
for (const v of adj[u]) {
if (!visitato[v]) {
[Link](‘${u} ${v}‘); // tree edge
DFS(v);
} else {
if (!terminato[v])
[Link](‘arco back ${u} ${v}‘);
}
}
terminato[u] = true;
}
Durante l’esecuzione, gli archi vengono classificati. Quando si visita un nodo v per la prima volta da u, l’arco (u, v)
è un arco dell’albero DFS. Se invece si incontra un nodo già visitato ma non ancora terminato, l’arco viene classificato
come arco all’indietro.
La funzione scansione permette di eseguire la DFS su tutte le componenti del grafo:
function scansione() {
visitato = Array(N).fill(false);
terminato = Array(N).fill(false);
for (let s = 0; s < N; s++)
if (!visitato[s]) DFS(s);
}
Nell’esempio in figura, l’albero DFS è evidenziato con archi marcati. Questi archi corrispondono esattamente a
quelli stampati dalla riga [Link](‘uv‘) durante la visita.
Gli altri archi del grafo vengono classificati in base allo stato dei nodi al momento dell’esplorazione. In particolare,
gli archi che collegano un nodo a un suo antenato nella ricorsione DFS sono archi back. Questo spiega la presenza di
archi che “risalgono” nell’albero nella figura.
L’ordine in cui i nodi vengono visitati dipende dall’ordine delle liste di adiacenza. Questo è un punto importante:
cambiando l’ordine degli elementi in adj[u] si ottiene un albero DFS diverso.
3 Visita BFS
La visita BFS (Breadth-First Search) esplora il grafo per livelli, partendo da un nodo sorgente s. Si visitano prima
tutti i nodi a distanza uno, poi quelli a distanza due, e così via.
Nel codice, la BFS è implementata utilizzando una coda:
function BFS(s) {
let visitato = Array(N).fill(false);
let queue = [];
visitato[s] = true;
[Link](s);
while ([Link] > 0) {
const u = [Link]();
for (const v of adj[u])
if (!visitato[v]) {
visitato[v] = true;
[Link](‘${u} ${v}‘);
[Link](v);
}
}
}
La coda garantisce che i nodi vengano visitati in ordine di distanza dalla sorgente. Gli archi stampati sono quelli
dell’albero BFS.
A differenza della DFS, la BFS costruisce un albero che rappresenta i cammini minimi (in termini di numero di
archi) dal nodo sorgente agli altri nodi raggiungibili.
4 Esempio completo
Il seguente codice costruisce un grafo orientato, lo stampa, esegue la DFS su tutte le componenti e infine una BFS a
partire dal nodo 0:
function main() {
const numNodes = 8;
2
const edges = [
[0, 1],
[0, 6],
[6, 7],
[7, 2],
[2, 3],
[7, 4],
[6, 5],
[2, 1],
[7, 1],
[7, 3],
[4, 3],
[5, 4],
[5, 6]
];
leggiGrafoOrientato(numNodes, edges);
stampaGrafo();
scansione();
BFS(0);
}
Il grafo ha N = 8 nodi, numerati da 0 a 7, ed è orientato con M = 12 archi. La chiamata a leggiGrafoOrientato
costruisce la lista di adiacenza, cioè per ogni nodo u memorizza i nodi raggiungibili con un arco uscente da u. In questo
caso, la lista di adiacenza è quella mostrata prima in figura:
0: 1 6
1:
2: 3 1
3:
4: 3
5: 4 6
6: 7 5
7: 2 4 1 3
Questo significa, per esempio, che dal nodo 0 partono gli archi (0, 1) e (0, 6), mentre dal nodo 7 partono gli archi
(7, 2), (7, 4), (7, 1) e (7, 3).
La funzione scansione() esegue una DFS completa del grafo. Si parla di DFS completa perché il ciclo esterno
prova a iniziare una visita da ogni nodo da 0 a N − 1, ma lancia realmente DFS(s) solo se il nodo s non è ancora stato
visitato. In questo modo si visitano tutte le componenti raggiungibili, anche se il grafo non fosse connesso.
In questo esempio la visita parte dal nodo 0, perché è il primo nodo non visitato. Da qui inizia la costruzione
dell’albero DFS.
Osserviamo con attenzione cosa accade passo passo.
Quando viene chiamata DFS(0), il nodo 0 viene marcato come visitato. A questo punto si esamina la sua lista di
adiacenza nell’ordine in cui compare, cioè prima il nodo 1 e poi il nodo 6.
Il primo vicino di 0 è 1. Poiché 1 non è ancora visitato, l’arco (0, 1) diventa un arco dell’albero DFS, viene stampato
come tree edge, e si richiama ricorsivamente DFS(1).
Entrati in DFS(1), il nodo 1 viene segnato come visitato. Tuttavia la sua lista di adiacenza è vuota, quindi non ci
sono altri nodi da esplorare. La visita di 1 termina subito e il nodo viene marcato come terminato. A questo punto
l’esecuzione ritorna alla chiamata precedente, cioè a DFS(0).
Riprendendo l’esplorazione dei vicini di 0, il prossimo nodo è 6. Anche 6 non era stato ancora visitato, quindi l’arco
(0, 6) entra nell’albero DFS e si richiama DFS(6).
Nel nodo 6 la lista di adiacenza è 7 5. Il primo vicino è 7. Siccome 7 non è ancora visitato, l’arco (6, 7) è un nuovo
arco dell’albero DFS e si prosegue con DFS(7).
Nel nodo 7 la lista di adiacenza è 2 4 1 3. Il primo vicino è 2. Anche in questo caso il nodo non era stato ancora
visitato, quindi (7, 2) è un arco dell’albero e si entra in DFS(2).
Nel nodo 2 la lista di adiacenza è 3 1. Il primo vicino è 3. Poiché 3 non è ancora visitato, l’arco (2, 3) entra
nell’albero DFS e si visita ricorsivamente il nodo 3.
Il nodo 3 non ha archi uscenti. Quindi la sua visita termina immediatamente e si ritorna a DFS(2). A questo punto
resta da esaminare il secondo vicino di 2, cioè 1. Però 1 è già stato visitato e, inoltre, è già stato terminato. Per questo
l’arco (2, 1) non può entrare nell’albero DFS. Non genera una nuova chiamata ricorsiva e non modifica la struttura
dell’albero.
Terminata l’esplorazione di tutti i vicini di 2, anche 2 viene marcato come terminato e si torna a DFS(7).
Riprendiamo ora la visita dal nodo 7. Dopo il vicino 2, il prossimo vicino nella lista è 4. Il nodo 4 non è ancora
visitato, quindi l’arco (7, 4) entra nell’albero DFS e si richiama DFS(4).
Nel nodo 4 la lista di adiacenza contiene solo 3. Ma il nodo 3 è già stato visitato ed è anche terminato. Quindi
l’arco (4, 3) non appartiene all’albero DFS. Terminata l’unica possibilità di esplorazione, anche 4 viene marcato come
terminato e si ritorna a DFS(7).
3
A questo punto nella lista di adiacenza di 7 rimangono ancora i nodi 1 e 3. Entrambi sono già stati visitati e già
terminati, quindi gli archi (7, 1) e (7, 3) non sono archi dell’albero DFS.
Quando tutti i vicini di 7 sono stati esaminati, il nodo 7 viene terminato e si torna a DFS(6).
Nel nodo 6 resta ancora da esaminare il vicino 5. Il nodo 5 non è ancora stato visitato, dunque l’arco (6, 5) entra
nell’albero DFS e si richiama DFS(5).
Nel nodo 5 la lista di adiacenza è 4 6. Il primo vicino è 4, ma 4 è già stato visitato e terminato, quindi l’arco
(5, 4) non entra nell’albero. Il secondo vicino è 6. In questo momento 6 è già visitato ma non è ancora terminato,
perché la sua chiamata ricorsiva è ancora attiva. Di conseguenza l’arco (5, 6) viene riconosciuto dal codice come un
arco back. Questo è coerente con l’idea generale della DFS: un arco back collega un nodo a un suo antenato nell’albero
di ricorsione.
Dopo avere esaminato tutti i vicini di 5, anche 5 viene terminato. Si ritorna quindi a DFS(6), che ora può terminare.
Subito dopo termina anche DFS(0).
A questo punto la componente raggiungibile da 0 è stata completamente esplorata. Il ciclo nella funzione scansione()
prosegue con i nodi successivi, ma sono ormai tutti già visitati. La DFS completa termina quindi senza avviare nuove
visite.
Raccogliendo nell’ordine gli archi che hanno effettivamente generato una nuova chiamata ricorsiva, otteniamo
l’albero DFS:
(0,1)
(0,6)
(6,7)
(7,2)
(2,3)
(7,4)
(6,5)
Questi sono esattamente gli archi stampati dal programma come tree edge. L’albero DFS non contiene tutti gli
archi del grafo, ma solo quelli che sono serviti a scoprire per la prima volta ciascun nodo.
Si vede quindi bene come l’albero non dipenda solo dalla struttura del grafo, ma anche dall’ordine in cui i vicini
compaiono nelle liste di adiacenza. Se, per esempio, nella lista del nodo 6 il vicino 5 comparisse prima di 7, la visita
cambierebbe e anche l’albero DFS risultante sarebbe diverso.
Dopo la DFS, il programma esegue anche BFS(0). In questo caso la visita non segue la profondità della ricorsione,
ma procede per livelli a partire dal nodo sorgente 0. Per questo motivo l’albero BFS ha in generale una struttura
diversa dall’albero DFS. Nel nostro esempio, la DFS costruisce un cammino di esplorazione profondo che si inoltra
lungo i successori dei nodi, mentre la BFS privilegia i nodi più vicini a 0 in termini di numero di archi.
Questo esempio mette dunque in evidenza la differenza fondamentale tra le due strategie di visita. La DFS esplora
un ramo fino in fondo prima di tornare indietro e produce un albero legato alla ricorsione. La BFS, invece, visita il
grafo per strati successivi e produce un albero dei cammini minimi dal nodo sorgente, quando tutti gli archi hanno lo
stesso costo.
APPENDICE
/**
* Grafi con N nodi numerati da 0 a N-1, e M archi
*/
let adj = [];
let N = 0;
let M = 0;
function leggiGrafoNonOrientato(numNodes, edges) {
N = numNodes;
M = [Link];
adj = [Link]({ length: N }, () => []); // crea un array di N array vuoti
for (const [u, v] of edges) {
adj[u].push(v);
adj[v].push(u); // va messo perche’ non orientato
}
}
function leggiGrafoOrientato(numNodes, edges) {
N = numNodes;
M = [Link];
adj = [Link]({ length: N }, () => []); // crea un array di N array vuoti
for (const [u, v] of edges)
adj[u].push(v);
4
}
function stampaGrafo() {
[Link]("GRAFO\n");
[Link]("liste di adiacenza");
for (let u = 0; u < N; u++) {
let riga = ‘${u}: ‘;
for (const v of adj[u]) riga += ‘${v} ‘;
[Link](riga);
}
[Link]("");
}
/* visita DFS */
let visitato = [];
let terminato = [];
function DFS(u) {
visitato[u] = true;
for (const v of adj[u]) {
if (!visitato[v]) {
[Link](‘${u} ${v}‘); // tree edge
DFS(v);
} else {
if (!terminato[v])
[Link](‘arco back ${u} ${v}‘);
}
}
terminato[u] = true;
}
function scansione() {
visitato = Array(N).fill(false);
terminato = Array(N).fill(false);
[Link]("Albero DFS:");
for (let s = 0; s < N; s++)
if (!visitato[s]) DFS(s);
[Link]("");
}
/* visita BFS da un nodo s */
function BFS(s) {
let visitato = Array(N).fill(false);
let queue = [];
visitato[s] = true;
[Link](s);
[Link](‘Albero BFS a partire dal nodo ${s}:‘);
while ([Link] > 0) {
const u = [Link](); // dequeue
for (const v of adj[u])
if (!visitato[v]) {
visitato[v] = true;
[Link](‘${u} ${v}‘); // tree edge
[Link](v);
}
}
}
function main() {
const numNodes = 8;
const edges = [
[0, 1],
[0, 6],
[6, 7],
[7, 2],
[2, 3],
5
[7, 4],
[6, 5],
[2, 1],
[7, 1],
[7, 3],
[4, 3],
[5, 4],
[5, 6]
];
leggiGrafoOrientato(numNodes, edges);
stampaGrafo();
scansione();
BFS(0);
}
main();