Algoritmi di visita di un grafo - Dipartimento di Ingegneria dell

Algoritmi di visita di un grafo
Ilaria Castelli
[email protected]
Università degli Studi di Siena
Dipartimento di Ingegneria dell’Informazione
A.A. 2009/2010
I. Castelli
Visita di un grafo, A.A. 2009/2010
1/44
Grafi
Visita in ampiezza
Visita in profondità
Ordinamento topologico
I. Castelli
Visita di un grafo, A.A. 2009/2010
2/44
Scopo e tipi di visita di un grafo
Visita
Una visita (o attraversamento) di un grafo G permette di esaminare i
nodi e gli archi di G in modo sistematico.
Esistono varie tipologie di visita, con diverse proprietà.
In particolare:
1
Visita in ampiezza (BFS = Breadth First Search)
2
Visita in profondità (DFS = Depth First Search)
I. Castelli
Visita di un grafo, A.A. 2009/2010
3/44
Breadth First Search
Visita in ampiezza
Dato un grafo G = (V, E) e un nodo s chiamato sorgente, la visita in
ampiezza esplora gli archi di G per scoprire tutti i nodi raggiungibili a
partire da s
La visita BFS calcola la distanza (numero minimo di archi) tra s e
ogni vertice da esso raggiungibile
La visita consente di definire un albero BFS, con radice s,
contenente tutti i nodi raggiungibili
Nell’ albero BFS il cammino da s a un nodo v corrisponde a un
cammino minimo (contenente il numero minimo di archi)
La visita BFS si può applicare sia ai grafi diretti che a quelli non diretti
I. Castelli
Visita di un grafo, A.A. 2009/2010
4/44
Breadth First Search
La visita in ampiezza esplora i nodi del grafo partendo da quelli a distanza
1 da s. Poi visita quelli a distanza 2, e cosı̀ via.
L’algoritmo visita tutti i vertici ad un livello k prima di visitare quelli a
livello k + 1.
distanza = 3
distanza = 2
i
distanza = 1
Si genera un albero
h
v
r
Si visitano nodi via via più
distanti dalla sorgente
s
w
t
u
x
y
I. Castelli
Visita di un grafo, A.A. 2009/2010
5/44
Breadth First Search
Per tenere traccia del progresso della visita, l’algoritmo BFS associa
delle “flag” ai nodi. Supponiamo di poter colorare i nodi di bianco,
grigio o nero.
All’inizio tutti i nodi sono bianchi e, successivamente, possono
diventare grigi e, infine, neri.
Un nodo viene scoperto la prima volta che viene incontrato durante
la visita e, in tale istante, cessa di essere bianco.
La distinzione tra nodi grigi e neri esiste affinché la visita proceda in
ampiezza.
In sostanza, la distinzione è la seguente:
I
I
I
I. Castelli
Bianchi: non ancora scoperti
Grigi: appena scoperti; sono la frontiera tra nodi scoperti e non. I nodi
adiacenti ad un nodo grigio possono essere bianchi.
Neri: scoperti. Tutti i nodi adiacenti ad un nodo nero sono stati
scoperti.
Visita di un grafo, A.A. 2009/2010
6/44
Algoritmo BFS - Strutture dati
Le strutture dati usate dall’algoritmo sono le seguenti:
Liste di adiacenza “Adj”
Adj[u] è la lista dei nodi adiacenti a u.
Array “color”
color[u] contiene il colore del nodo u
Array “d”
d[u] contiene la distanza di u dal nodo sorgente s. Viene inizializzata
a “infinito”.
Array “p”
p[u] contiene il predecessore del nodo u nell’albero BFS
Coda “Q”
contiene i nodi grigi
I. Castelli
Visita di un grafo, A.A. 2009/2010
7/44
Algoritmo BFS
1
2
3
4
5
BFS (G , s )
f o r o g n i nodo u i n V [ G ] − { s } /∗ i n i z i a l i z z a z i o n e ∗/
c o l o r [ u ] = WHITE
d[u] = infinity
p [ u ] = NIL
6
7
8
9
10
11
12
13
14
15
16
17
18
19
20
c o l o r [ s ] = GRAY /∗ v i s i t o l a s o r g e n t e ∗/
d[ s ] = 0
p [ s ] = NIL
Q = {s}
w h i l e Q != empty
u = head [Q] /∗ nodo da e s p a n d e r e ∗/
f o r o g n i nodo v i n Adj [ u ] /∗ v i s i t o i n o d i a d i a c e n t i ∗/
i f c o l o r [ v ] = WHITE /∗ s e e ’ b i a n c o v i e n e s c o p e r t o ∗/
t h e n c o l o r [ v ] = GRAY
d[v] = d[u] + 1
p[v] = u
ENQUEUE(Q, v ) /∗ i n s e r i t o n e l l a coda Q ∗/
DEQUEUE(Q) /∗ t o l t o d a l l a coda : e ’ g i a ’ s t a t o e s p a n s o ∗/
c o l o r [ u ] = BLACK
I. Castelli
Visita di un grafo, A.A. 2009/2010
8/44
Algoritmo BFS - Esempio
d
r
p
inf
r NIL
inf
s NIL
Adj
−
u
r
v
s
inf
s
r
w −
inf
t NIL
t
w
x
u inf
u NIL
u
t
v
inf
v NIL
v
r
w inf
w NIL
inf
inf
inf
inf
w
s
x
inf
x NIL
v
w
x
y
x
w
y
inf
y NIL
Q = {}
y
u
x
s
t
I. Castelli
r
s
inf
inf
t
inf
Visita di un grafo, A.A. 2009/2010
u
−
t
x
−
t
y
−
y
−
−
−
9/44
Algoritmo BFS - Esempio
d
r
p
inf
r NIL
0
s NIL
Adj
−
u
r
v
s
inf
s
r
w −
inf
t NIL
t
w
x
u inf
u NIL
u
t
v
inf
v NIL
v
r
w inf
w NIL
inf
inf
inf
inf
w
s
x
inf
x NIL
v
w
x
y
x
w
y
inf
y NIL
Q = {s}
y
u
x
s
t
I. Castelli
r
inf
s
0
t
inf
Visita di un grafo, A.A. 2009/2010
u
−
t
x
−
t
y
−
y
−
−
−
9/44
Algoritmo BFS - Esempio
p
d
r
1
r
0
s NIL
s
Adj
−
u
r
v
s
inf
s
r
w −
inf
t NIL
t
w
x
u inf
u NIL
u
t
v
inf
v NIL
v
r
w
1
w
s
x
w
y
u
x
s
t
x
y
w
s
r
1
s
0
t
inf
inf
1
inf
inf
inf
x NIL
v
w
x
y
inf
y NIL
Q = {w, r}
I. Castelli
Visita di un grafo, A.A. 2009/2010
u
−
t
x
−
t
y
−
y
−
−
−
9/44
Algoritmo BFS - Esempio
p
d
r
s
t
1
r
0
s NIL
2
t
s
Adj
r
1
s
0
t
2
r
v
s
inf
s
r
w −
t
w
x
w
u
−
t
x
−
t
y
−
u inf
u NIL
u
t
v
inf
v NIL
v
r
w
w
s
x
w
y
u
x
1
w
x
2
x
y
inf
I. Castelli
s
inf
1
2
inf
w
v
w
x
y
y NIL
−
u
Q = {r, t, x}
Visita di un grafo, A.A. 2009/2010
y
−
−
−
9/44
Algoritmo BFS - Esempio
p
d
r
s
t
1
r
0
s NIL
2
t
s
Adj
r
1
s
0
t
2
r
v
s
inf
s
r
w −
t
w
x
w
u
−
t
x
−
t
y
−
u inf
u NIL
u
t
v
2
v
r
v
r
w
s
2
1
2
inf
w
s
w
v
w
x
y
x
w
y
u
x
1
w
x
2
x
y
inf
I. Castelli
y NIL
−
u
Q = {t, x, v}
Visita di un grafo, A.A. 2009/2010
y
−
−
−
9/44
Algoritmo BFS - Esempio
p
d
r
s
1
r
0
s NIL
s
Adj
r
1
s
0
t
2
r
v
s
3
s
r
w −
w
x
2
t
w
t
u
3
u
t
u
t
v
2
v
r
v
r
w
s
2
1
2
inf
w
s
w
v
w
x
y
x
w
y
u
x
t
1
w
x
2
x
y
inf
I. Castelli
y NIL
−
u
Q = {x, v, u}
Visita di un grafo, A.A. 2009/2010
u
−
t
x
−
t
y
−
y
−
−
−
9/44
Algoritmo BFS - Esempio
p
d
r
s
1
r
0
s NIL
s
Adj
r
1
s
0
t
2
r
v
s
3
s
r
w −
w
x
2
t
w
t
u
3
u
t
u
t
v
2
v
r
v
r
w
w
s
x
w
y
u
x
t
1
w
s
2
1
2
3
x
2
x
w
v
w
x
y
y
3
y
x
Q = {v, u, y}
I. Castelli
−
u
Visita di un grafo, A.A. 2009/2010
u
−
t
x
−
t
y
−
y
−
−
−
9/44
Algoritmo BFS - Esempio
p
d
r
s
1
r
0
s NIL
s
Adj
r
1
s
0
t
2
r
v
s
3
s
r
w −
w
x
2
t
w
t
u
3
u
t
u
t
v
2
v
r
v
r
w
w
s
x
w
y
u
x
t
1
w
s
2
1
2
3
x
2
x
w
v
w
x
y
y
3
y
x
Q = {u, y}
I. Castelli
−
u
Visita di un grafo, A.A. 2009/2010
u
−
t
x
−
t
y
−
y
−
−
−
9/44
Algoritmo BFS - Esempio
p
d
r
s
1
r
0
s NIL
s
Adj
r
1
s
0
t
2
r
v
s
3
s
r
w −
w
x
2
t
w
t
u
3
u
t
u
t
v
2
v
r
v
r
w
w
s
x
w
y
u
x
t
1
w
s
2
1
2
3
x
2
x
w
v
w
x
y
y
3
y
x
Q = {y}
I. Castelli
−
u
Visita di un grafo, A.A. 2009/2010
u
−
t
x
−
t
y
−
y
−
−
−
9/44
Algoritmo BFS - Esempio
p
d
r
s
1
r
0
s NIL
s
Adj
r
1
s
0
t
2
r
v
s
3
s
r
w −
w
x
2
t
w
t
u
3
u
t
u
t
v
2
v
r
v
r
w
w
s
x
w
y
u
x
t
1
w
s
2
1
2
3
x
2
x
w
v
w
x
y
y
3
y
x
Q = {}
I. Castelli
−
u
Visita di un grafo, A.A. 2009/2010
u
−
t
x
−
t
y
−
y
−
−
−
9/44
Algoritmo BFS - Albero BFS
La visita BFS consente di definire un albero BFS.
all’inizio contiene solo s
quando un nodo bianco v viene scoperto, scorrendo la lista di
adiacenza di un nodo u, allora l’arco (u, v) e v stesso vengono
aggiunti all’albero
p(r) = s
r
p(s) = NIL
s
p(t) = w
t
p(u) = t
u
1
0
2
3
2
1
v
p(v) = r
w
p(w) = s
I. Castelli
2
x
p(x) = w
s
r
1
v
2
0
w
1
x
2
t
2
y
3
u
3
3
y
p(y) = x
Visita di un grafo, A.A. 2009/2010
10/44
Breadth First Search - Analisi
Analisi del tempo di esecuzione su un grafo G = (V, E)
Il tempo necessario per l’inizializzazione è O(| V |)
Ogni nodo raggiungibile viene visitato una volta
I
I
Le operazioni di inserimento e rimozione dalla coda costano O(1),
quindi il tempo totale necessario per le operazioni sulla coda è O(| V |)
La lista di adiacenza di un nodo viene scorsa una sola volta, quindi in
totale il tempo è O(| E |)
Il tempo totale richiesto dall’algoritmo BFS si ottiene sommando il tempo
per l’inizializzazione e quello necessario per visitare i nodi:
O(| V | + | E |)
I. Castelli
Visita di un grafo, A.A. 2009/2010
11/44
Breadth First Search - Cammini minimi
Distanza minima
Si definisce distanza minima δ(s, v) da s a v, il numero minimo di archi
di un cammino dal nodo s al nodo v
δ(s, v) ≥ 0
δ(s, v) = ∞ se v non è raggiungibile partendo da s
Cammino minimo
Un cammino di lunghezza δ(s, v) da s a v si dice cammino minimo.
Nota: possono esistere più cammini minimi tra due nodi
BFS
La visita BFS calcola la distanza minima δ(s, v) di ogni nodo v
raggiungibile da s
Nell’albero BFS il cammino da s ad un nodo v è un cammino
minimo
I. Castelli
Visita di un grafo, A.A. 2009/2010
12/44
Breadth First Search - Proprietà
Lemma
Dato un grafo G = (V, E) diretto o non diretto e un nodo s ∈ V qualsiasi,
allora per ogni arco (u, v) ∈ E si ha
δ(s, v) ≤ δ(s, u) + 1
Dimostrazione
Se u non è raggiungibile da s, allora δ(s, u) = ∞
Se u è raggiungibile da s, allora anche v è raggiungibile.
Il cammino minimo da s a v non può essere più lungo del cammino
minimo da s a u, più l’arco (u, v)
I. Castelli
Visita di un grafo, A.A. 2009/2010
13/44
Breadth First Search - Proprietà
Lemma
Sia G = (V, E) un grafo diretto o non diretto e s ∈ V un nodo sorgente
qualsiasi, a partire dal quale è stato eseguito l’algoritmo BFS. Allora per
ogni nodo v ∈ V si ha
d[v] ≥ δ(s, v)
Dimostrazione Per induzione:
d[s] = 0 = δ(s, s) e, per qualsiasi nodo v ∈ V − {s}, vale
d[v] = ∞ ≥ δ(s, v)
Dato un nodo v scoperto durante l’esplorazione di un nodo u, per
ipotesi induttiva vale d[u] ≥ δ(s, u).
d[v] |{z}
= d[u] + 1
algoritmo
I. Castelli
≥
|{z}
δ(s, u) + 1
ipotesi induttiva
Visita di un grafo, A.A. 2009/2010
≥
|{z}
δ(s, v)
lemma precedente
14/44
Breadth First Search - Proprietà
Lemma
Supponendo che durante l’esecuzione della ricerca BFS su un grafo
G = (V, E), la coda Q contenga i nodi < v1 , . . . , vr >, dove v1 = head[Q]
e vr = tail[Q], allora
d[vr ] ≤ d[v1 ] + 1
e
d[vi ] ≤ d[vi+1 ],
i = 1, . . . , r − 1
La differenza tra le distanze da s dei nodi presenti nella coda in un
certo momento è al più 1
Un nodo v viene inserito nella coda (diventando vr+1 ) quando il nodo
in testa, v1 , viene esplorato
d[vr+1 ] = d[v] = d[v1 ] + 1
d[vr ] ≤ d[v1 ] + 1 = d[v] = d[vr+1 ]
I. Castelli
Visita di un grafo, A.A. 2009/2010
15/44
Breadth First Search - Proprietà
Proposizione
I nodi che entrano nella coda Q sono tutti e soli i nodi u tali che
δ(s, u) < ∞, cioè tutti i nodi raggiungibili da s
Dimostrazione
1 v entra in Q =⇒ δ(s, v) < ∞
Si procede per induzione sull’i-esima iterazione dell’operazione
EN QU EU E
I
I
se i = 0, solo s è nella coda: δ(s, s) = 0 < ∞
se i > 0, supponiamo che l’ipotesi induttiva sia vera per ogni iterazione
k < i.
Al passo i si visita Adj[u], con u = head[Q], e i nodi bianchi vengono
inseriti in Q. Per ipotesi induttiva δ(s, u) < ∞.
Poiché esiste l’arco (u, v):
δ(s, v) ≤ δ(s, u) + 1 < ∞
I. Castelli
Visita di un grafo, A.A. 2009/2010
16/44
Breadth First Search - Proprietà
2
v entra in Q ⇐= δ(s, v) < ∞
Si procede per induzione su δ(s, v) = k
I
I
se δ(s, v) = 0 è vero: v = s
se δ(s, v) = k > 0, per ipotesi induttiva si ha che per ogni u tale che
δ(s, u) < k, u è già entrato in coda.
Poiché δ(s, v) < ∞, esiste un cammino < v0 , . . . , vi−1 , vi > da s a v,
con v0 = s e vi = v.
s
v0
v(i−1)
v
δ(s, vi−1 ) = k − 1 e vi−1 è nella coda per ipotesi induttiva.
Quando verrà visitata Adj[vi−1 ] verrà scoperto v e:
F
F
I. Castelli
se è bianco entra in coda
v non può essere grigio o nero, altrimenti sarebbe già entrato in coda,
perché varrebbe δ(s, v) < k !
Visita di un grafo, A.A. 2009/2010
17/44
Breadth First Search - Albero BFS
Albero BFS
L’array p definisce un sottografo dei predecessori di G. In particolare, si
tratta di un albero, Tp :
Tp = (Vp , Ep )
Vp = {v ∈ V : p[v] 6= N IL} ∪ {s}
Ep = {(p[v], v) ∈ E : v ∈ Vp − {s}}
Una volta eseguita la ricerca BFS, la seguente procedura stampa il
cammino minimo da s a v
1
2
3
4
5
6
7
PRINT−PATH(G , s , v )
if v = s
then p r i n t s
e l s e i f p [ v ] = NIL
t h e n p r i n t " non esiste un cammino da s a v"
e l s e PRINT−PATH(G , s , p [ v ] )
print v
I. Castelli
Visita di un grafo, A.A. 2009/2010
18/44
Depth First search
Visita in profondità
Dato un grafo G = (V, E) ed un nodo s, detto nodo sorgente, la visita
depth first esplora il grafo andando il più possibile in profondità.
Dato un nodo v appena scoperto, la visita prosegue a partire da v sui
suoi archi che ancora non sono stati esplorati
Quando si sono esplorati tutti gli archi del nodo v, si torna al nodo
dal quale v è stato scoperto, e si esplorano i suoi ulteriori archi non
ancora esplorati (se ce ne sono)
Si prosegue finchè non vengono scoperti tutti i nodi raggiungibili da s
Se vi sono ancora dei nodi non scoperti, uno di questi viene adottato
come una nuova sorgente, e la visita riprende a partire da esso
L’algoritmo termina quando tutti i nodi sono stati scoperti
I. Castelli
Visita di un grafo, A.A. 2009/2010
19/44
Depth First Search
Per tenere traccia del progresso della visita, anche l’algoritmo DFS
associa delle “flag” ai nodi. Di nuovo, si suppone di colorare i nodi di
bianco, grigio o nero.
All’inizio tutti i nodi sono bianchi e, successivamente, possono
diventare grigi e, infine, neri.
Un nodo viene scoperto la prima volta che viene incontrato durante
la visita e, in tale istante, cessa di essere bianco.
La distinzione tra nodi grigi e neri è necessaria affinché la visita
proceda in profondità.
La distinzione è la seguente:
I
I
I
I. Castelli
Bianchi: non ancora scoperti
Grigi: sono stati scoperti, ma l’esplorazione della loro lista di adiacenza
non è ancora terminata.
Neri: l’esplorazione della loro lista di adiacenza è completata.
Visita di un grafo, A.A. 2009/2010
20/44
Algoritmo DFS - Strutture dati
Le strutture dati usate dall’algoritmo sono le seguenti:
Liste di adiacenza “Adj”
Adj[u] è la lista dei nodi adiacenti a u.
Array “color”
color[u] contiene il colore del nodo u
Array “p”
p[u] contiene il predecessore del nodo u nella foresta DFS
Array “d”
d[u] è un timestamp che contiene il momento in cui u è stato
scoperto.
Array “f”
f [u] è un timestamp che contiene il momento in cui si è conclusa la
visita di u, cioè si è finito di esaminare al sua lista di adiacenza Adj[u].
I. Castelli
Visita di un grafo, A.A. 2009/2010
21/44
Algoritmo DFS - Strutture dati
Nota: Il nodo u è
bianco prima di d[u]
grigio tra d[u] e f [u]
nero dopo f [u]
Ovviamente si ha d[u] < f [u], ∀u ∈ V
I timestamp sono numeri interi compresi tra 1 e 2 | V |, poiché ogni nodo
viene scoperto esattamente una volta, e si finisce di esplorarlo esattamente
una volta.
I. Castelli
Visita di un grafo, A.A. 2009/2010
22/44
Algoritmo DFS
1
2
3
4
5
6
7
8
1
2
3
4
5
6
7
8
9
10
11
DFS(G , s )
f o r o g n i v e r t i c e u i n V [ G ] /∗ i n i z i a l i z z a z i o n e ∗/
c o l o r [ u ] = WHITE
p [ u ] = NIL
time = 0
for ogni v e r t i c e u in V[G]
i f c o l o r [ u ] = WHITE
t h e n DFS−VISIT ( u ) /∗ v i s i t a o g n i nodo non s c o p e r t o ∗/
DFS−VISIT ( u )
c o l o r [ u ] = GRAY
d [ u ] = t i m e /∗ tempo d i i n i z i o v i s i t a l i s t a d i a d i a c e n z a ∗/
time = time + 1
f o r o g n i v e r t i c e v i n Adj [ u ]
i f c o l o r [ v ] = WHITE
then p [ v ] = u
DFS−VISIT ( v ) /∗ v i s i t a s u b i t o n o d i non s c o p e r t i ∗/
c o l o r [ u ] = BLACK /∗ f i n i t o d i v i s i t a r e i n o d i a d i a c e n t i ∗/
f [ u ] = time
time = time + 1
I. Castelli
Visita di un grafo, A.A. 2009/2010
23/44
Algoritmo DFS - Esempio
Adj
u
x
I. Castelli
v
y
w
z
u
v
v
y −
w
y
x
v
−
y
x
−
z
z
−
Visita di un grafo, A.A. 2009/2010
x
−
z
−
24/44
Algoritmo DFS - Esempio
u
v
w
y
z
1/
x
I. Castelli
Visita di un grafo, A.A. 2009/2010
25/44
Algoritmo DFS - Esempio
u
v
w
1/
x
I. Castelli
y
z
u
v
1/
2/
x
y
w
z
Visita di un grafo, A.A. 2009/2010
25/44
Algoritmo DFS - Esempio
u
v
w
1/
u
v
1/
2/
w
u
v
1/
2/
w
3/
x
I. Castelli
y
z
x
y
z
Visita di un grafo, A.A. 2009/2010
x
y
z
25/44
Algoritmo DFS - Esempio
u
v
w
1/
u
v
1/
2/
w
u
v
1/
2/
w
3/
x
y
z
w
u
v
1/
2/
4/
3/
x
y
I. Castelli
x
y
z
x
y
z
z
Visita di un grafo, A.A. 2009/2010
25/44
Algoritmo DFS - Esempio
u
v
w
1/
u
v
1/
2/
w
u
v
1/
2/
w
3/
x
y
z
u
v
w
1/
2/
x
y
z
u
v
w
1/
2/
x
y
z
B
4/
3/
x
y
I. Castelli
z
4/
3/
x
y
z
Visita di un grafo, A.A. 2009/2010
25/44
Algoritmo DFS - Esempio
u
v
w
1/
u
v
1/
2/
w
u
v
1/
2/
w
3/
x
y
z
u
v
w
1/
2/
x
y
z
u
v
w
1/
2/
x
y
z
u
v
w
1/
2/
B
4/
3/
x
y
I. Castelli
z
B
4/
3/
x
y
z
Visita di un grafo, A.A. 2009/2010
4/5
3/
x
y
z
25/44
Algoritmo DFS - Esempio
u
v
w
1/
u
v
1/
2/
w
u
v
1/
2/
w
3/
x
y
z
u
v
w
1/
2/
x
y
z
u
v
w
1/
2/
x
y
z
u
v
w
1/
2/
B
4/
3/
x
y
z
v
w
u
1/
B
4/
3/
x
y
z
4/5
3/
x
y
z
2/
B
4/5
3/6
x
y
I. Castelli
z
Visita di un grafo, A.A. 2009/2010
25/44
Algoritmo DFS - Esempio
u
v
w
1/
u
v
1/
2/
w
u
v
1/
2/
w
3/
x
y
z
u
v
w
1/
2/
x
y
z
u
v
w
1/
2/
x
y
z
u
v
w
1/
2/
B
4/
3/
x
y
z
v
w
u
1/
2/
4/
3/
x
y
z
v
w
u
1/
B
4/5
3/
x
y
z
2/7
B
4/5
3/6
x
y
I. Castelli
B
4/5
z
x
3/6
y
z
Visita di un grafo, A.A. 2009/2010
25/44
Algoritmo DFS - Esempio
u
v
w
1/
u
v
1/
2/
w
u
v
1/
2/
w
3/
x
y
z
u
v
w
1/
2/
x
y
z
u
v
w
1/
2/
x
y
z
u
v
w
1/
2/
B
4/
3/
x
y
z
v
w
u
1/
2/
4/
3/
x
y
z
v
w
u
1/
B
2/7
3/6
x
y
4/5
z
x
4/5
3/
x
y
z
v
w
u
1/
B
4/5
I. Castelli
B
F
3/6
y
z
Visita di un grafo, A.A. 2009/2010
2/7
B
4/5
3/6
x
y
z
25/44
Algoritmo DFS - Esempio
u
v
1/8
F
2/7
B
4/5
3/6
x
y
I. Castelli
w
z
Visita di un grafo, A.A. 2009/2010
26/44
Algoritmo DFS - Esempio
u
v
1/8
F
2/7
u
F
3/6
x
y
v
1/8
B
4/5
I. Castelli
w
z
2/7
w
9/
B
4/5
3/6
x
y
z
Visita di un grafo, A.A. 2009/2010
26/44
Algoritmo DFS - Esempio
u
v
1/8
F
2/7
u
F
3/6
x
y
v
1/8
B
4/5
I. Castelli
w
z
2/7
w
9/
B
u
1/8
F
4/5
3/6
x
y
z
Visita di un grafo, A.A. 2009/2010
v
w
2/7
B
9/
C
4/5
3/6
x
y
z
26/44
Algoritmo DFS - Esempio
u
v
1/8
F
w
2/7
F
3/6
x
y
z
u
v
w
1/8
2/7
B
2/7
w
9/
B
u
1/8
F
4/5
3/6
x
y
z
v
w
2/7
B
9/
C
4/5
3/6
x
y
z
9/
C
4/5
3/6
x
y
I. Castelli
v
1/8
B
4/5
F
u
10/
z
Visita di un grafo, A.A. 2009/2010
26/44
Algoritmo DFS - Esempio
u
v
1/8
F
w
2/7
F
3/6
x
y
z
u
v
w
1/8
2/7
B
3/6
x
y
I. Castelli
9/
C
4/5
v
1/8
B
4/5
F
u
w
2/7
F
3/6
x
y
z
u
v
w
1/8
2/7
B
v
1/8
9/
B
4/5
F
u
w
2/7
B
9/
C
4/5
3/6
x
y
z
9/
C
10/
4/5
3/6
z
x
y
10/
z B
Visita di un grafo, A.A. 2009/2010
26/44
Algoritmo DFS - Esempio
u
v
1/8
F
w
2/7
F
3/6
x
y
z
u
v
w
1/8
2/7
B
3/6
x
y
I. Castelli
9/
C
4/5
v
1/8
B
4/5
F
u
z
2/7
F
3/6
x
y
z
u
v
w
1/8
2/7
4/5
x
u
B
9/
C
3/6
y
v
1/8
9/
B
4/5
F
10/
w
z B
Visita di un grafo, A.A. 2009/2010
2/7
B
9/
C
4/5
3/6
x
y
z
u
v
w
1/8
2/7
F
10/
w
B
9/
C
4/5
3/6
x
y
10/11
z B
26/44
Algoritmo DFS - Esempio
u
v
1/8
F
w
2/7
F
3/6
x
y
z
u
v
w
1/8
2/7
B
9/
C
4/5
3/6
x
y
10/
z
u
v
w
2/7
9/12
B
2/7
F
x
y
z
u
v
w
1/8
2/7
x
B
9/
C
3/6
y
v
1/8
9/
B
3/6
4/5
u
z B
2/7
B
9/
C
4/5
3/6
x
y
z
u
v
w
1/8
2/7
F
10/
w
B
9/
C
4/5
3/6
x
y
10/11
z B
C
4/5
3/6
x
y
I. Castelli
w
4/5
F
1/8
F
v
1/8
B
4/5
F
u
10/11
z B
Visita di un grafo, A.A. 2009/2010
26/44
Foresta DFS
Allo stesso modo della ricerca BFS, nella ricerca DFS, un nodo v viene
scoperto esplorando la lista di adiacenza di un nodo u già scoperto.
L’array “p” tiene traccia del predecessore di ogni nodo scoperto: p[v] = u
Foresta DFS
L’array p definisce un sottografo dei predecessori di G. In particolare, si
tratta di una foresta, Fp :
Fp = (V, Ep )
Ep = {(p[v], v) : v ∈ V e p[v] 6= N IL}
Il sottografo dei predecessori è una foresta depth first, costituita da più
alberi depth first.
I. Castelli
Visita di un grafo, A.A. 2009/2010
27/44
Foresta DFS - Classificazione degli archi
Gli archi del grafo originario vengono classificati in:
Tree-edge. Archi della foresta DFS.
Forward-edge. Archi in avanti.
Archi non appartenenti alla foresta DFS, che vanno da un vertice ad
un suo successore nella foresta DFS. Quando vengono percorsi
durante l’algoritmo DFS, collegano due nodi già scoperti.
Backward-edge. Archi all’indietro.
Archi non appartenenti alla foresta DFS, che vanno da un vertice ad
un suo antenato nella foresta DFS. Archi del grafo che, quando
vengono percorsi durante l’algoritmo DFS, collegano due nodi già
scoperti.
Cross-edge Archi di attraversamento.
Tutti gli altri archi. Collegano due nodi che non hanno una relazione
di discendenza l’uno dall’altro.
I. Castelli
Visita di un grafo, A.A. 2009/2010
28/44
Foresta DFS
p
u
v
w
1/8
2/7
9/12
F
B
3/6
x
y
v
9/12 w
2/7 v
10/11 z
F
u
C
w NIL
C
4/5
u NIL
1/8 u
10/11
z B
x
y
y
v
z
w
B
B
3/6 y
4/5 x
La struttura degli alberi DFS rispecchia esattamente la struttura delle chiamate
ricorsive alla procedura DF S − V ISIT : u = p[v] se e solo se DF S − V ISIT (v)
è stata chiamata durante lo scorrimento della lista di adiacenza di u.
Nota: gli archi uscenti ed entranti sullo stesso nodo (self-loop), vengono
considerati backward-edge.
I. Castelli
Visita di un grafo, A.A. 2009/2010
29/44
Algoritmo DFS - Analisi
1
Nella procedura DF S ci sono due cicli, che vengono eseguiti Θ(| V |)
2
La procedura DF S − V ISIT viene richiamata esattamente una volta
per ogni nodo v ∈ V
3
Durante l’esecuzione di DF S − V ISIT (u), il ciclo nelle linee 5-8
viene eseguito |Adj[u]| volte
4
Poiché
X
| Adj[v] |= Θ(| E |)
v∈V
il costo totale per l’esecuzione del ciclo è Θ(| E |)
Il tempo totale di esecuzione è Θ(| V | + | E |)
I. Castelli
Visita di un grafo, A.A. 2009/2010
30/44
Algoritmo DFS - Proprietà
Teorema delle parentesi
In una visita in profondità di un grafo (diretto o non diretto) G = (V, E),
per ogni coppia di nodi u e v, definiamo gli intervalli
A = [d[u], f [u]]
B = [d[v], f [v]]
Allora, una e una sola delle seguenti condizioni è vera:
1
A∩B =∅
2
L’intervallo A è interamente incluso nell’intervallo B, e u è un
discendente di v in un albero DFS
3
L’intervallo B è interamente incluso nell’intervallo A, e v è un
discendente di u in un albero DFS
I. Castelli
Visita di un grafo, A.A. 2009/2010
31/44
Algoritmo DFS - Proprietà
Dimostrazione
1 Caso 1. d[u] < d[v]. Ci sono due sottocasi:
1
d[v] < f [u]
F
F
F
F
F
u viene scoperto prima di v
Quando si scopre v la visita di u non è stata completata (u è grigio)
Ciò vuol dire che v è discendente di u
Poiché v è stato scoperto più recentemente di u, la visita di v deve
completarsi prima di tornare a u: f [v] < f [u]
QUindi l’intervallo A = [d[u], f [u]] è completamente contenuto in
B = [d[v], f [v]]
d[u]
I. Castelli
d[v]
f[v]
Visita di un grafo, A.A. 2009/2010
f[u]
32/44
Algoritmo DFS - Proprietà
1
2
d[v] > f [u]
F
F
F
F
u diventa nero prima che v venga scoperto
Quindi, quando v viene scoperto la visita di u è già stata completata
d[v] < f [v] e d[u] < f [u]
Quindi gli intervalli A = [d[u], f [u]] e B = [d[v], f [v]] sono disgiunti
d[u]
2
I. Castelli
f[u]
d[v]
f[v]
Caso 2. d[u] > d[v]: è simmetrico, basta scambiare il ruolo di u e v
Visita di un grafo, A.A. 2009/2010
33/44
Algoritmo DFS - Proprietà
1
2
d[v] > f [u]
F
F
F
F
u diventa nero prima che v venga scoperto
Quindi, quando v viene scoperto la visita di u è già stata completata
d[v] < f [v] e d[u] < f [u]
Quindi gli intervalli A = [d[u], f [u]] e B = [d[v], f [v]] sono disgiunti
d[u]
2
f[u]
d[v]
f[v]
Caso 2. d[u] > d[v]: è simmetrico, basta scambiare il ruolo di u e v
Corollario (consegue dal teorema delle parentesi)
Un nodo v è un discendente di un nodo u in un albero della foresta DFS
per un grafo (diretto o non diretto) G se e solo se
d[u] < d[v] < f [v] < f [u]
I. Castelli
Visita di un grafo, A.A. 2009/2010
33/44
Algoritmo DFS - Proprietà
1/8 u
9/12 w
2/7 v
10/11 z
u
w
v
z
F
C
B
B
y
3/6 y
x
4/5 x
1
I. Castelli
2
3
4
Visita di un grafo, A.A. 2009/2010
5
6
7
8
9
10 11 12
34/44
Algoritmo DFS - Un altro esempio
y
z
s
t
3/6
2/9
1/10
11/16
B
C
4/5
s
t
11/16
C
z
B
F
2/9
C
v
s
B
v
t
z
v
u
14/15
C
y
7/8
w
x
C
I. Castelli
u
w
3/6
x 4/5
B
C 14/15
u
12/13
y
C
C 12/13
7/8
w
x
1/10
F
1
2
3
4
5
6
Visita di un grafo, A.A. 2009/2010
7
8
9
10 11 12 13 14 15 16
35/44
Algoritmo DFS - Proprietà
Teorema del cammino bianco
In una foresta DFS, un nodo v è discendente di u se e solo se al tempo
d[u] (in cui la visita scopre u), il vertice v è raggiungibile da u con un
cammino contenente esclusivamente nodi bianchi.
d[u]/
v’
I. Castelli
Visita di un grafo, A.A. 2009/2010
v
36/44
Algoritmo DFS - Classificazione degli archi
L’algoritmo DFS può essere modificato in modo da effettuare una
classificazione degli archi. Ogni arco può essere classificato in funzione del
colore del vertice che raggiunge, quando viene percorso per la prima volta:
Archi bianchi. Quelli appartenenti a un albero DFS.
Archi grigi. Archi backward. Uniscono due nodi grigi durante la
visita DFS.
Archi neri. Archi forward (se d[u] < d[v]) oppure crossward (se
d[u] > d[v]).
Nota: in un grafo non diretto ci possono essere ambiguità perché (u, v) e
(v, u) sono lo stesso arco. In tal caso l’arco viene classificato come l’arco
orientata (u, v) oppure (v, u), a seconda della direzione in cui viene
percorso per la prima volta.
I. Castelli
Visita di un grafo, A.A. 2009/2010
37/44
Algoritmo DFS - Classificazione degli archi
Teorema
Se G è un grafo non orientato, allora ogni arco è un tree-edge oppure un
backward-edge.
Dimostrazione.
Sia (u, v) un arco arbitrario
Supponiamo d[u] < d[v] (senza perdita di generalità)
Allora si verifica uno di questi due casi:
1
2
I. Castelli
(u, v) viene visitato a partire da u, con u grigio e v bianco. In tal caso
è un tree-edge.
(u, v) viene visitato a partire da v, con v e u entrambi grigi. In tal caso
è un backward-edge.
Visita di un grafo, A.A. 2009/2010
38/44
Algoritmo DFS - Classificazione degli archi
Lemma
Un grafo diretto è aciclico se e solo se l’algoritmo DFS non determina
l’esistenza di backward-edge
Dimostrazione.
1
=⇒. Se (u, v) è un arco all’indietro, allora v è un antenato di
u nella foresta DFS. Quindi, esiste un cammino da v a u in G,
e l’arco backward (u, v) completa il ciclo.
2
⇐=. Si suppone che G abbia un ciclo c. Sia v il primo vertice
del ciclo ad essere scoperto, e sia (u, v) l’arco che lo precede
nel ciclo. Al tempo d[v] tutti i nodi da v a u sono bianchi (v
grigio). Per il teorema dei cammini bianchi u sarà un
discendente di v. Quindi, (u, v) è necessariamente un
backward-edge.
x
B
y
z
u
I. Castelli
v
Visita di un grafo, A.A. 2009/2010
39/44
Ordinamento topologico
L’algoritmo DFS può essere usato per effettuare un ordinamento
topologoco dei nodi di un grafo diretto aciclico (DAG - Direct Acyclic
Graph).
Ordinamento topologico
Un ordinamento topologico di un DAG G = (V, E) è un ordinamento
lineare dei suoi vertici tale che, se G contiene un arco (u, v), allora u
compare prima di v nell’ordinamento.
Se il grafo contenesse dei cicli, un ordinamento di questo tipo non sarebbe
possibile.
I. Castelli
Visita di un grafo, A.A. 2009/2010
40/44
Ordinamento topologico
1
4
I. Castelli
2
1
3
4
2
4
1
3
2
1
4
3
2
3
Visita di un grafo, A.A. 2009/2010
41/44
Ordinamento topologico
1
2
3
4
5
6
TOPOLOGICAL−SORT(G)
Chiama DFS(G) p e r c a l c o l a r e i t e m p i d i f i n e v i s i t a f [ v ]
per ogni v e r t i c e v
Appena l a v i s i t a d i un nodo e ’ finita , inseriscilo
in testa a una lista concatenata
Restituisci la lista concatenata dei nodi
Supponendo che s = 2 e Adj[s] = 4 → 3 → 1
1
2
4
3
f [2] > f [1] > f [3] > f [4]
2
1
3
4
Nota: l’ordinamento topologico ottenuto varia a seconda della sorgente
scelta, e dall’ordine dei nodi nelle liste Adj
I. Castelli
Visita di un grafo, A.A. 2009/2010
42/44
Ordinamento topologico
Teorema
T OP OLOGICAL − SORT (G) produce un ordinamento topologico di un
grafo orientato aciclico G
Dimostrazione.
È sufficiente dimostrare che per ogni coppia di vertici u, v ∈ V , se
esiste un arco (u, v), allora f [v] < f [u]
Poiché il grafo è aciclico, non esistono backward-edge (archi grigi).
Quindi (u, v) può essere:
1
2
I. Castelli
un arco bianco (tree-edge). In tal caso v è bianco e diventa
discendente di u e, per il teorema delle parentesi, f [v] < f [u]
un arco nero (forward-edge oppure cross-edge). In tal caso v è nero e
f [v] < f [u] perché v è già diventato nero prima di aver concluso la
visita di u.
Visita di un grafo, A.A. 2009/2010
43/44
Ordinamento topologico - Analisi
DF S(G) richiede tempo Θ(| V | + | E |)
L’inserimento di ognuno dei | V | nodi nella lista richiede tempo
costante.
L’ordinamento topologico richiede tempo Θ(| V | + | E |)
I. Castelli
Visita di un grafo, A.A. 2009/2010
44/44