Visita in profondità partendo da A
grafo
A
A
B
B
A--B
8
C
C
A--C
10
D
D
A--D
4
E
E
A--E
5
G
G
A--G
2
B--D
1
B--E
9
C--G
6
F
F
C--F
5
E--G
4
F--G
3
Inizializzazione
Si usa una struttura dati di tipo Stack
Inserimento del nodo A
Stack: [A/0]
Visitati: []
grafo
A
A
0
B
B
-1
A--B
8
C
C
-1
A--C
10
D
D
-1
A--D
4
E
E
-1
A--E
5
G
G
-1
A--G
2
B--D
1
B--E
9
C--G
6
F
F
-1
C--F
5
E--G
4
F--G
3
Elaborazione dei nodi inseriti in Stack finchè non sono esauriti
Estrazione e visita del nodo A
Stack: []
Storico Stack: [A/0]
grafo
A
A
0
B
B
-1
A--B
8
C
C
-1
A--C
10
D
D
-1
A--D
4
E
E
-1
A--E
5
G
G
-1
A--G
2
B--D
1
B--E
9
C--G
6
F
F
-1
C--F
5
E--G
4
F--G
3
Nodi adiacenti a A non ancora visitati
Inserimento in Stack del nodo adiacente non visitato B
(A->B)
Inserimento in Stack del nodo adiacente non visitato C
(A->C)
Inserimento in Stack del nodo adiacente non visitato D
(A->D)
Inserimento in Stack del nodo adiacente non visitato E
(A->E)
Inserimento in Stack del nodo adiacente non visitato G
(A->G)
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
-1
C--F
5
E--G
4
F--G
3
Stack: [G/1, E/1, D/1, C/1, B/1]
Visitati: [A/0]
Storico Stack: [G/1, E/1, D/1, C/1, B/1, A/0]
Estrazione e visita del nodo G
Stack: [E/1, D/1, C/1, B/1]
Storico Stack: [G/1, E/1, D/1, C/1, B/1, A/0]
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
-1
C--F
5
E--G
4
F--G
3
Nodi adiacenti a G non ancora visitati
Inserimento in Stack del nodo adiacente non visitato C
(G->C)
Inserimento in Stack del nodo adiacente non visitato E
(G->E)
Inserimento in Stack del nodo adiacente non visitato F
(G->F)
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3
Stack: [F/2, E/1, C/1, E/1, D/1, C/1, B/1]
Visitati: [A/0, G/1]
Storico Stack: [F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Estrazione e visita del nodo F
Stack: [E/1, C/1, E/1, D/1, C/1, B/1]
Storico Stack: [F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3
Nodi adiacenti a F non ancora visitati
Inserimento in Stack del nodo adiacente non visitato C
(F->C)
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3
Stack: [C/1, E/1, C/1, E/1, D/1, C/1, B/1]
Visitati: [A/0, G/1, F/2]
Storico Stack: [C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Estrazione e visita del nodo C
Stack: [E/1, C/1, E/1, D/1, C/1, B/1]
Storico Stack: [C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3
Nodi adiacenti a C non ancora visitati
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3
Stack: [E/1, C/1, E/1, D/1, C/1, B/1]
Visitati: [A/0, G/1, F/2, C/1]
Storico Stack: [C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Estrazione e visita del nodo E
Stack: [C/1, E/1, D/1, C/1, B/1]
Storico Stack: [C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3
Nodi adiacenti a E non ancora visitati
Inserimento in Stack del nodo adiacente non visitato B
(E->B)
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3
Stack: [B/1, C/1, E/1, D/1, C/1, B/1]
Visitati: [A/0, G/1, F/2, C/1, E/1]
Storico Stack: [B/1, C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Estrazione e visita del nodo B
Stack: [C/1, E/1, D/1, C/1, B/1]
Storico Stack: [B/1, C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3
Nodi adiacenti a B non ancora visitati
Inserimento in Stack del nodo adiacente non visitato D
(B->D)
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3
Stack: [D/1, C/1, E/1, D/1, C/1, B/1]
Visitati: [A/0, G/1, F/2, C/1, E/1, B/1]
Storico Stack: [D/1, B/1, C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Estrazione e visita del nodo D
Stack: [C/1, E/1, D/1, C/1, B/1]
Storico Stack: [D/1, B/1, C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3
Nodi adiacenti a D non ancora visitati
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3
Stack: [C/1, E/1, D/1, C/1, B/1]
Visitati: [A/0, G/1, F/2, C/1, E/1, B/1, D/1]
Storico Stack: [D/1, B/1, C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Estrazione e visita del nodo C
Il nodo C è già stato visitato. Passo al prossimo nodo se presente in Stack
Stack: [E/1, D/1, C/1, B/1]
Storico Stack: [D/1, B/1, C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Estrazione e visita del nodo E
Il nodo E è già stato visitato. Passo al prossimo nodo se presente in Stack
Stack: [D/1, C/1, B/1]
Storico Stack: [D/1, B/1, C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Estrazione e visita del nodo D
Il nodo D è già stato visitato. Passo al prossimo nodo se presente in Stack
Stack: [C/1, B/1]
Storico Stack: [D/1, B/1, C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Estrazione e visita del nodo C
Il nodo C è già stato visitato. Passo al prossimo nodo se presente in Stack
Stack: [B/1]
Storico Stack: [D/1, B/1, C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Estrazione e visita del nodo B
Il nodo B è già stato visitato. Passo al prossimo nodo se presente in Stack
Stack: []
Storico Stack: [D/1, B/1, C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Stack è vuota. Arresto
Storico della Stack
[D/1, B/1, C/1, F/2, E/1, C/1, G/1, E/1, D/1, C/1, B/1, A/0]
Ordine di visita dei nodi
[A/0, G/1, F/2, C/1, E/1, B/1, D/1]
grafo
A
A
0
B
B
1/A
A--B
8
C
C
1/A
A--C
10
D
D
1/A
A--D
4
E
E
1/A
A--E
5
G
G
1/A
A--G
2
B--D
1
B--E
9
C--G
6
F
F
2/G
C--F
5
E--G
4
F--G
3