Visita in ampiezza partendo da S
grafo
M
M
P
P
M--P
Y
Y
M--Y
R
R
P--R
X
X
P--X
R--X
S
S
R--S
X--Y
T
T
S--T
U
U
T--U
Inizializzazione
Si usa una struttura dati di tipo Queue
Inserimento del nodo S
Queue: [S/0]
Visitati: []
grafo
M
M
-1
P
P
-1
M--P
Y
Y
-1
M--Y
R
R
-1
P--R
X
X
-1
P--X
R--X
S
S
0
R--S
X--Y
T
T
-1
S--T
U
U
-1
T--U
Elaborazione dei nodi inseriti in Queue finchè non sono esauriti
Estrazione e visita del nodo S
Queue: []
Storico Queue: [S/0]
grafo
M
M
-1
P
P
-1
M--P
Y
Y
-1
M--Y
R
R
-1
P--R
X
X
-1
P--X
R--X
S
S
0
R--S
X--Y
T
T
-1
S--T
U
U
-1
T--U
Nodi adiacenti a S non ancora visitati
Inserimento in Queue del nodo adiacente non visitato R
(S->R)
Inserimento in Queue del nodo adiacente non visitato T
(S->T)
grafo
M
M
-1
P
P
-1
M--P
Y
Y
-1
M--Y
R
R
1/S
P--R
X
X
-1
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
-1
T--U
Queue: [R/1, T/1]
Visitati: [S/0]
Storico Queue: [S/0, R/1, T/1]
Estrazione e visita del nodo R
Queue: [T/1]
Storico Queue: [S/0, R/1, T/1]
grafo
M
M
-1
P
P
-1
M--P
Y
Y
-1
M--Y
R
R
1/S
P--R
X
X
-1
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
-1
T--U
Nodi adiacenti a R non ancora visitati
Inserimento in Queue del nodo adiacente non visitato P
(R->P)
Inserimento in Queue del nodo adiacente non visitato X
(R->X)
grafo
M
M
-1
P
P
2/R
M--P
Y
Y
-1
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
-1
T--U
Queue: [T/1, P/2, X/2]
Visitati: [S/0, R/1]
Storico Queue: [S/0, R/1, T/1, P/2, X/2]
Estrazione e visita del nodo T
Queue: [P/2, X/2]
Storico Queue: [S/0, R/1, T/1, P/2, X/2]
grafo
M
M
-1
P
P
2/R
M--P
Y
Y
-1
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
-1
T--U
Nodi adiacenti a T non ancora visitati
Inserimento in Queue del nodo adiacente non visitato U
(T->U)
grafo
M
M
-1
P
P
2/R
M--P
Y
Y
-1
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U
Queue: [P/2, X/2, U/2]
Visitati: [S/0, R/1, T/1]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2]
Estrazione e visita del nodo P
Queue: [X/2, U/2]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2]
grafo
M
M
-1
P
P
2/R
M--P
Y
Y
-1
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U
Nodi adiacenti a P non ancora visitati
Inserimento in Queue del nodo adiacente non visitato M
(P->M)
Inserimento in Queue del nodo adiacente non visitato X
(P->X)
grafo
M
M
3/P
P
P
2/R
M--P
Y
Y
-1
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U
Queue: [X/2, U/2, M/3, X/2]
Visitati: [S/0, R/1, T/1, P/2]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2]
Estrazione e visita del nodo X
Queue: [U/2, M/3, X/2]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2]
grafo
M
M
3/P
P
P
2/R
M--P
Y
Y
-1
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U
Nodi adiacenti a X non ancora visitati
Inserimento in Queue del nodo adiacente non visitato Y
(X->Y)
grafo
M
M
3/P
P
P
2/R
M--P
Y
Y
3/X
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U
Queue: [U/2, M/3, X/2, Y/3]
Visitati: [S/0, R/1, T/1, P/2, X/2]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2, Y/3]
Estrazione e visita del nodo U
Queue: [M/3, X/2, Y/3]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2, Y/3]
grafo
M
M
3/P
P
P
2/R
M--P
Y
Y
3/X
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U
Nodi adiacenti a U non ancora visitati
grafo
M
M
3/P
P
P
2/R
M--P
Y
Y
3/X
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U
Queue: [M/3, X/2, Y/3]
Visitati: [S/0, R/1, T/1, P/2, X/2, U/2]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2, Y/3]
Estrazione e visita del nodo M
Queue: [X/2, Y/3]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2, Y/3]
grafo
M
M
3/P
P
P
2/R
M--P
Y
Y
3/X
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U
Nodi adiacenti a M non ancora visitati
Inserimento in Queue del nodo adiacente non visitato Y
(M->Y)
grafo
M
M
3/P
P
P
2/R
M--P
Y
Y
3/X
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U
Queue: [X/2, Y/3, Y/3]
Visitati: [S/0, R/1, T/1, P/2, X/2, U/2, M/3]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2, Y/3, Y/3]
Estrazione e visita del nodo X
Il nodo X è già stato visitato. Passo al prossimo nodo se presente in Queue
Queue: [Y/3, Y/3]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2, Y/3, Y/3]
Estrazione e visita del nodo Y
Queue: [Y/3]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2, Y/3, Y/3]
grafo
M
M
3/P
P
P
2/R
M--P
Y
Y
3/X
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U
Nodi adiacenti a Y non ancora visitati
grafo
M
M
3/P
P
P
2/R
M--P
Y
Y
3/X
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U
Queue: [Y/3]
Visitati: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, Y/3]
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2, Y/3, Y/3]
Estrazione e visita del nodo Y
Il nodo Y è già stato visitato. Passo al prossimo nodo se presente in Queue
Queue: []
Storico Queue: [S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2, Y/3, Y/3]
Queue è vuota. Arresto
Storico della Queue
[S/0, R/1, T/1, P/2, X/2, U/2, M/3, X/2, Y/3, Y/3]
Ordine di visita dei nodi
[S/0, R/1, T/1, P/2, X/2, U/2, M/3, Y/3]
grafo
M
M
3/P
P
P
2/R
M--P
Y
Y
3/X
M--Y
R
R
1/S
P--R
X
X
2/R
P--X
R--X
S
S
0
R--S
X--Y
T
T
1/S
S--T
U
U
2/T
T--U