Visita in profondità o
Depth-First-Search (DFS)
La struttura dati D è una PILA (STACK)
Master Bioinformatica 2002: Visite di Grafi
B
H
C
A
D
A
G
B
C
E
S
H
G
F
D
C
B
A
F
D
F
G
H
Master Bioinformatica 2002: Visite di Grafi
B
H
C
A
D
AA
G
B
C
E
S
H
G
F
D
C
B
A
F
D
F
G
H
Master Bioinformatica 2002: Visite di Grafi
B
H
C
A
D
AA
G
B
C
E
F
D
F
S
F
D
C
B
A
G
H
Master Bioinformatica 2002: Visite di Grafi
B
H
C
A
D
AA
G
B
C
E
S
E
F
D
C
B
A
F
D
F
G
H
Master Bioinformatica 2002: Visite di Grafi
G
E
B
H
C
A
D
AA
G
B
C
E
F
D
F
S
F
D
C
B
A
G
H
Master Bioinformatica 2002: Visite di Grafi
G
E
B
H
C
A
D
AA
G
B
C
E
F
D
F
S
D
C
B
A
G
H
Master Bioinformatica 2002: Visite di Grafi
G
E
B
H
C
A
D
AA
G
B
C
E
F
D
F
S
C
B
A
G
H
Master Bioinformatica 2002: Visite di Grafi
E
B
H
C
A
D
AA
G
B
C
E
F
D
F
G
S
B
A
H
Master Bioinformatica 2002: Visite di Grafi
E
B
H
C
A
D
AA
G
B
C
E
F
D
F
G
S
A
H
Master Bioinformatica 2002: Visite di Grafi
E
B
H
C
A
D
AA
G
B
C
E
F
D
F
G
H
S
Master Bioinformatica 2002: Visite di Grafi
E
Vertici memorizzati nelle liste di adiacenza in ordine alfabetico:
CONSIDERIAMO L’ORDINE IN CUI I VERTICI
DIVENTANO GRIGI: viene creato l’albero
1
AA 8
2
B
7
3
C
6
4
D
5
5
F
4
E L’ORDINE IN CUI DIVENTANO NERI
B
1
A
7
2
H
3
8E
C
D
G
6
4
5
F
6 G 2 8
7
Master Bioinformatica 2002: Visite di Grafi
H 1
E 3
1 A 16
Usando un unico contatore si ottiene:
B
1
A
2 7
8
3
8
2 B 15
3
E
7
C
6
D
4
5
5
1
H
6
3 C 14
G
2
4 D 13
5 F 12
4F
6 G 9
7 H 8
Master Bioinformatica 2002: Visite di Grafi
10 E 11
Visita DFS (prima versione)
DFS-VISITA (G, s)
S  make_empty_stack
color s  gray
push (S, s)
while not_empty (S) do
u  top (S)
if c’è v bianco adiacente a u
then color v  gray
P[v  u
push (S, v)
else color u  black
pop (S)
Master Bioinformatica 2002: Visite di Grafi
Seconda versione con ciclo sugli adiacenti sul top dello stack
top(S)
cambia
ogni volta
che viene
aggiunto
un vertice
DFS-VISITA (G, s)
S  make_empty_stack
color s  gray
push (S, s)
while not_empty (S) do
while c’è un v adiacente a top (S)
non considerato do
if color v = white
then color v  gray
P[v  top(S)
push (S, v)
color top(S)  black
pop (S)
Master Bioinformatica 2002: Visite di Grafi
D
A
A
C
B
D
B
F
C
E
F
C
F
B
S
D
A
Master Bioinformatica 2002: Visite di Grafi
D
A
A
C
B
D
B
F
E
F
E
F
B
S
D
A
Master Bioinformatica 2002: Visite di Grafi
C
C
E
D
A
A
C
B
D
B
F
E
F
C
E
F
B
S
D
A
Master Bioinformatica 2002: Visite di Grafi
C
C
E
E
D
A
A
C
B
D
B
F
C
C
E
E
E
F
C
E
F
B
S
D
A
Master Bioinformatica 2002: Visite di Grafi
F
D
A
A
C
B
D
B
F
C
C
E
E
E
F
F
B
S
D
A
Master Bioinformatica 2002: Visite di Grafi
D
A
A
C
B
D
B
F
C
C
E
E
E
F
F
B
D
S
A
Master Bioinformatica 2002: Visite di Grafi
D
A
A
D
C
B
B
F
C
C
E
E
E
F
F
B
D
A
S
Master Bioinformatica 2002: Visite di Grafi
Osservazione
A
D
B
F
Gli intervalli di “attivazione” di due
vertici sono:
• disgiunti
• uno interamente contenuto
C
C
E
E
nell’altro
F
B
D
A
Master Bioinformatica 2002: Visite di Grafi
un vertice non viene “disattivato”
finchè non sono stati ‘attivati”e
poi “disattivati” tutti i suoi discendenti
1 A 12
2 D 11
3 B 10
è l’ordine in cui si percorre l’albero
delle chiamate ricorsive di una
procedura ricorsiva
4 F 9
5 C 6
7 E 8
Versione ricorsiva dell’algoritmo
di visita in profondità
Master Bioinformatica 2002: Visite di Grafi
DFS-VISITA-ricorsiva (G, u)
color u  gray
while c’è v adiacente a u non considerato do
if color v = white
then P[v  u
DFS-VISITA-ricorsiva (G, v)
color u  black
Master Bioinformatica 2002: Visite di Grafi
C'è corrispondenza fra lo stack della procedura
iterativa e lo stack delle attivazioni della procedura
ricorsiva.
Più precisamente, supponendo che gli adiacenti
vengano visitati nello stesso ordine dalle due
procedure, se ad un certo punto dell'esecuzione lo
stack della procedura iterativa è <v1, v2, ..., vr> (con
v1= s e vr sul top), la corrispondente sequenza di
attivazioni per la procedura ricorsiva sarà:
<DFS-visit (G,v1), ..., DFS-visit (G,vr)>.
Master Bioinformatica 2002: Visite di Grafi
D
DFS-ric(G,A)
A
C
B
DFS-ric(G,D)
DFS-ric(G,B)
DFS-ric(G,F)
E
F
DFS-ric(G,C)
C
F
B
S
D
A
Master Bioinformatica 2002: Visite di Grafi
D
DFS-ric(G,A)
A
C
B
DFS-ric(G,D)
DFS-ric(G,B)
DFS-ric(G,F)
E
F
DFS-ric(G,C)
C
F
B
S
D
A
Master Bioinformatica 2002: Visite di Grafi
D
DFS-ric(G,A)
A
C
B
DFS-ric(G,D)
DFS-ric(G,B)
DFS-ric(G,F)
E
F
F
B
S
D
A
Master Bioinformatica 2002: Visite di Grafi
D
DFS-ric(G,A)
A
C
B
DFS-ric(G,D)
DFS-ric(G,B)
DFS-ric(G,F)
E
F
DFS-ric(G,E)
E
F
B
S
D
A
Master Bioinformatica 2002: Visite di Grafi
D
DFS-ric(G,A)
A
C
B
DFS-ric(G,D)
DFS-ric(G,B)
DFS-ric(G,F)
E
F
F
B
S
D
A
Master Bioinformatica 2002: Visite di Grafi
D
DFS-ric(G,A)
A
C
B
DFS-ric(G,D)
DFS-ric(G,B)
E
F
S
B
D
A
Master Bioinformatica 2002: Visite di Grafi
D
DFS-ric(G,A)
A
C
B
DFS-ric(G,D)
E
F
S
D
A
Master Bioinformatica 2002: Visite di Grafi
D
DFS-ric(G,A)
A
C
B
E
F
S
A
Master Bioinformatica 2002: Visite di Grafi
D
A
C
B
E
F
S
Master Bioinformatica 2002: Visite di Grafi
DFS con calcolo dei tempi di inizio e fine visita
Introduciamo un contatore “time” per ricordare l’ordine
delle attivazioni e disattivazioni e i due attributi d (attivazione)
e f (disattivazione)
INIZIALIZZA (G)
for ogni u  V do
color u  white
P[u  nil
d[u]  
f[u]  
time  0
N.b. Se un vertice non viene “visitato” i suoi tempi di
attivazione e disattivazione resteranno infiniti.
Master Bioinformatica 2002: Visite di Grafi
DFS-VISITA-ricorsiva (G, u)
color u  gray
time  time + 1
d[u]  time
while c’è v adiacente a u non considerato do
if color v = white
then P[v  u
DFS-VISITA-ricorsiva (G, v)
time  time + 1
f[u]  time
color u  black
Master Bioinformatica 2002: Visite di Grafi
Proprietà della visita in profondità:
1. Teorema delle parentesi
In ogni visita DFS di un grafo (orientato o non orientato), per ogni
coppia di vertici u, v una e una sola delle seguenti condizioni è
soddisfatta:
 d[u] < d[v] < f[v] < f[u] e u è un antenato di v in un albero
della foresta DFS
 d[v] < d[u] < f[u] < f[v] e u è un discendente di v in un albero
della foresta DFS
 d[u] < f[u] < d[v] < f[v] e tra u e v non esiste relazione di
antenato - discendente
Master Bioinformatica 2002: Visite di Grafi
Classificazione degli archi del grafo durante una DFS
DEFINIZIONE
Arco dell’albero: arco inserito nella foresta DFS
Arco all’indietro: arco che collega un vertice ad un suo antenato
in un albero della foresta DFS
Arco in avanti:
arco che collega un vertice ad un suo discendente
in un albero della foresta DFS
Arco di attraversamento: arco che collega due vertici che non sono
in relazione antenato - discendente
Master Bioinformatica 2002: Visite di Grafi
OSSERVAZIONE
un arco (u, v) viene “percorso” quando si scopre v nella
lista degli adiacenti ad u.
In quel momento color[v] può essere:
• bianco: (u, v) è un arco dell’albero
• grigio: v è un antenato di u in un albero della foresta DFS,
(u, v) è un arco all’indietro
• nero:
la visita di v è già terminata, (u, v) è un arco
• in avanti se v è un discendente di u
in tal caso d[u] < d[v] < f[v] < f[u]
d[u] < d[v]
• di attraversamento altrimenti
in tal caso d[v] < f[v] < d[u] < f[u]
d[v] < d[u]
Master Bioinformatica 2002: Visite di Grafi
(Vertici adiacenti scanditi in ordine alfabetico)
A
B
D
C
E
Master Bioinformatica 2002: Visite di Grafi
(Vertici adiacenti scanditi in ordine alfabetico)
1
A
B
D
C
E
Master Bioinformatica 2002: Visite di Grafi
(Vertici adiacenti scanditi in ordine alfabetico)
1
A
2
B
D
C
E
Master Bioinformatica 2002: Visite di Grafi
(Vertici adiacenti scanditi in ordine alfabetico)
1
A
2
3
B
D
C
E
Master Bioinformatica 2002: Visite di Grafi
(Vertici adiacenti scanditi in ordine alfabetico)
1
(D, A) arco all’indietro
A
2
3 4
B
D
C
E
Master Bioinformatica 2002: Visite di Grafi
(Vertici adiacenti scanditi in ordine alfabetico)
1
(D, A) arco all’indietro
A
2 5
3 4
B
D
C
E
Master Bioinformatica 2002: Visite di Grafi
(Vertici adiacenti scanditi in ordine alfabetico)
1
(D, A) arco all’indietro
A
2 5
3 4
B
D
C
6
E
Master Bioinformatica 2002: Visite di Grafi
(D, A) arco all’indietro
1
(C, B) arco di attraversameto
A
2 5
3 4
B
D
C
6
E
Master Bioinformatica 2002: Visite di Grafi
(D, A) arco all’indietro
1
(C, B) arco di attraversameto
A
2 5
3 4
B
D
6
C
E
7
Master Bioinformatica 2002: Visite di Grafi
(D, A) arco all’indietro
(C, B) arco di attraversameto
1
(E, D) arco di attraversameto
A
2 5
3 4
B
D
C
6
E
7 8
Master Bioinformatica 2002: Visite di Grafi
(D, A) arco all’indietro
(C, B) arco di attraversameto
1
(E, D) arco di attraversameto
A
2 5
3 4
B
D
C
E
69
7 8
Master Bioinformatica 2002: Visite di Grafi
(D, A) arco all’indietro
(C, B) arco di attraversameto
1 10
(E, D) arco di attraversameto
A
(A, E) arco in avanti
2 5
3 4
B
D
C
E
6 9
7 8
Master Bioinformatica 2002: Visite di Grafi
Teorema
In una visita DFS di un grafo non orientato , ogni arco è un
arco dell’albero o un arco all’indietro.
Teorema
Un grafo, orientato o non orientato , è aciclico se e solo se una
visita DFS (qualunque) non produce archi all’indietro.
Master Bioinformatica 2002: Visite di Grafi
Ordinamento topologico di un DAG
Un ordinamento topologico di un DAG
G= (V, E) è un ordinamento di tutti i vertici
tale che
se c’è un arco (u, v) in E allora u precede v
Master Bioinformatica 2002: Visite di Grafi
Semplici applicazioni degli algoritmi di visita
• Algoritmo che determina se un grafo orientato
contiene un ciclo
• Algoritmo che determina se un grafo non orientato
e’ connesso
• Algoritmo che conta le componenti connesse di un
grafo non orientato
• Algoritmo che determina un ordinamento
topologico di un DAG
Master Bioinformatica 2002: Visite di Grafi
Esempio di DAG
slip
calze
orologio
pantaloni
scarpe
camicia
cintura
cravatta
giacca
Master Bioinformatica 2002: Visite di Grafi
Possibile ordinameto (non è unico)
slip
orologio
calze
pantaloni
camicia
scarpe
cintura
cravatta
giacca
Master Bioinformatica 2002: Visite di Grafi
Idea!
In un DAG, al termine di una visita DFS vale
per ogni arco (u,v)
f(u) > f(v)
Algoritmo: fai una visita DFS su tutto il grafo,
dai in outpu l’elenco dei vertici ordinati per
tempo f(u) di fine visita decrescente
Master Bioinformatica 2002: Visite di Grafi