Depth-first search
Visita in profondità di un grafo
Algoritmo
Esempio
Complessità dell’algoritmo
Proprietà
Ordinamento topologico
Depth-first search
Dato un grafo G=(V,E) e un specifico vertice s chiamato
sorgente, la visita in profondità (in inglese depth-first
search) esplora il grafo andando ogni volta il più
possibile in profondità.
•Per ogni vertice v in visita si prosegue la visita sugli
archi non ancora esplorati.
•Se sul vertice v in visita si sono esplorati tutti gli archi,
si torna al vertice di origine (padre).
•Se sul grafo rimane qualche vertice non scoperto si
ricomincia la visita in profondità su uno di quei vertici.
L’intero processo è ripetuto finché non vengono scoperti
tutti i vertici del grafo.
Depth-first search
Strutture dati utilizzate:
• Liste di adiacenza Adj: per conoscere i vertici adiacenti a
un vertice.
• color[u]: si colora il vertice u di bianco (vertice non
scoperto), di grigio (vertice appena scoperto) e di nero (ha
finito di visitare tutta la sua lista di Adiacenza).
• p[u]: il predecessore di u nella foresta DFS.
• d[u]: tempo in cui viene scoperto u.
• f[u]: tempo in cui viene finita la visita in u. Si ha d[u]<f[u].
Nota: u è bianco (WHITE) prima di d[u], grigio (GRAY) tra
d[u] e f[u], infine nero (BLACK) dopo f[u].
Algoritmo
DFS(G,s)
1.
for ogni vertice u in V[G]
2.
do color[u] ← WHITE
3.
p[u] ← NIL
4.
time ← 0
5.
for ogni vertice u in V[G]
6.
do if color[u] = WHITE
7.
then DFS-VISIT(u)
DFS-VISIT(u)
1.
color[u] ← GRAY
2.
d[u] ← time
3.
time ← time + 1
4.
for ogni vertice v in Adj[u]
5.
do if color[v] = WHITE
6.
then p[v] ← u
7.
DFS-VISIT(v)
8.
color[u] ← BLACK
9.
10.
f[u] ← time
time ← time + 1
// inizializzazione di ogni vertice
// visita da ogni vertice non ancora scoperto
// vertice diventa grigio, appena scoperto
// tempo inizio visita lista adiacenza
// visita subito vertice non ancora scoperto
// vertice diventa nero, ha visitato tutta
l’adiacenza
// tempo fine visita lista adiacenza
Esempio
u
v
w
u
1/
1/
(a)
v
u
w
1/
2/
v
w
2/
(c)
(b)
3/
x
y
z
x
y
z
x
y
z
u
v
w
u
v
w
u
v
w
1/
1/
2/
(d)
2/
3/
2/
4/5
3/
(f)
(e)
4/
1/
4/
3/
x
y
z
x
y
z
x
y
z
u
v
w
u
v
w
u
v
w
1/
1/
2/
2/7
(h)
(g)
4/5
x
y
z
2/7
4/5
3/6
(i)
4/5
3/6
1/
x
3/6
y
z
x
y
z
Esempio
u
1/8
v
u
w
1/8
2/7
v
2/7
w
9/
(m)
(l)
4/5
v
1/8
2/7
4/5
3/6
w
9/
(n)
4/5
3/6
u
3/6
x
y
z
x
y
z
x
y
z
u
v
w
u
v
w
u
v
w
1/8
2/7
9/
1/8
2/7
9/
(p)
(o)
4/5
3/6
10/
x
y
z
u
v
w
1/8
2/7
9/12
4/5
3/6
10/11
y
z
(r)
x
1/8
2/7
9/
4/5
3/6
10/11
y
z
(q)
4/5
x
3/6
10/
y
z
x
Complessità
Analisi del tempo di esecuzione:
• Ci sono due cicli in DFS() che vengono eseguiti Θ(|V|)
volte.
• DFS-VISIT(u) viene eseguito esattamente una volta per
ogni vertice in V.
• Durante l’esecuzione di DFS-VISIT(u) il ciclo nelle linee 47 viene eseguito |Adj[u]| volte. Poiché la somma di tutte le
liste di adiacenza è Θ(|E|), si ha che il costo totale del ciclo
in DFS-VISIT() è Θ(|E|).
• Quindi, il tempo totale di esecuzione è Θ(|V| + |E|).
Nota: come per il BFS si definisce degli alberi DFS
corrispondente al sottografo Gp definito dal vettore p.
Proprietà
Teorema delle parentesi
In ogni visita in profondità di un grafo G=(V,E), per ogni
coppia di nodi u,v in V, con A=[d[u], f[u]] e B=[d[v], f[v]].
Allora una e una sola delle seguenti condizioni è vera:
•
A B  
•
A  B e u è discendente di v in un albero DFS.
•
B  A e v è discendente di u in un albero DFS.
Dimostrazione
Proprietà
Caso d[u] < d[v]
Se d[v] < f[u], allora u diventa grigio prima di v, ma quando
viene scoperto v la visita ad u non è stata completata.
Questo implica che v è un discendente di u.
Poiché v è stato scoperto più recentemente di u, la visita in
v deve completarsi prima di ritornare a u, f[v] < f[u].
Quindi l’intervallo [d[v], f[v]] è completamente contenuto in
[d[u], f[u]].
u nero dopo
aver scoperto v
d[u] d[v]
f[v]
d[u] < f[u]
d[v] < f[v]
f[u]
Allora v è discendente di u:
la visita di v deve completarsi prima di quella di u
Proprietà
Dimostrazione
Caso d[u] < d[v]
Se f[u] < d[v], allora u diventa nero prima di v, ossia quando
viene scoperto v la visita ad u è stata completata. (d[v]<f[v])
Quindi l’intervallo [d[v], f[v]] è disgiunto da [d[u], f[u]].
Caso d[v] < d[u]: simmetrico.
u nero prima di
aver scoperto v
d[u] < f[u]
d[v] < f[v]
d[u]
f[u]
d[v]
f[v]
Quando è scoperto v la vista in u è stata completata.
Proprietà
Teorema del cammino bianco
In una foresta DFS di un grafo G=(V,E) un vertice 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
contenete esclusivamente nodi bianchi.
d[u]/
Cammino bianco
da u a v.
u
v
v discendente di u
Proprietà
Classificazione degli archi:
•Tree-edge (T, archi dell’albero): archi appartenenti alla
foresta DFS.
•Back-edge (B, archi all’indietro): archi non appartenenti
alla foresta DFS che vanno da un vertice v ad un suo
antenato u in un albero DFS.
•Forward-edge (F, archi in avanti): archi non appartenenti
alla foresta DFS che vanno da un vertice u ad un suo
successore v in un albero DFS.
•Cross-edge (C, archi di attraversamento): tutti gli altri
archi.
Proprietà
u
F
x
w
2/7
9/12
T
1/8
4/5
v
B
T
T
3/6
y
C
T: Tree-edge
B: Back-edge
F: Forward-edge
C: Cross-edge
T
10/11
z
B
Si modifica l’algoritmo DFS in modo che ogni arco (u,v) è:
•WHITE (bianco): se appartiene ad un albero DFS.
•GRAY (grigio): se è un arco all’indietro (unisce due vertici
grigi durante la DFS).
•BLACK (nero): se è un forward-edge (d[u] < d[v]) o un
cross-edge (d[u] > d[v]). E’ un arco che va verso un vertice
nero nel DFS().
Proprietà
Nota: nel caso di grafo non orientato l’arco viene classificato
come l’arco orientato (u,v) oppure (v,u), a seconda di quale
dei due viene scoperto per primo.
Proposizione
Se G è un grafo non orientato ogni arco o è un Treeedge oppure è un Back-edge.
Dimostrazione
Sia (u,v) un arco arbitrario di G.
Senza perdita di generalità, supponiamo d[u] < d[v].
Ci sono due casi:
Proprietà
1.L’arco (u,v) viene visitato a partire da u, u grigio e v
bianco. Allora (u,v) è classificato bianco (Tree-edge).
2.L’arco (u,v) viene visitato a partire da v, u e v grigi. Allora
(u,v) è classificato grigio (Back-edge).
Proposizione
Un grafo G contiene un ciclo se e solo se l’algoritmo
DFS determina l’esistenza di un Back-edge.
Dimostrazione
<=
Se (u,v) è un arco all’indietro, allora v è un antenato di u.
Esiste un cammino da v a u e l’arco (u,v), non appartenente
al cammino, completa il ciclo.
Proprietà
=>
G ha un ciclo c. Sia v il primo vertice del ciclo c ad essere
scoperto e sia (u,v) l’arco che lo precede in c.
Al tempo d[v] tutti i nodi da v a u sono bianchi (v grigio).
Per il teorema dei cammini bianchi il vertice u diventerà
discendente i v.
Durante la visita del vertice u l’arco (u,v) verrà
necessariamente classificato come grigio (Back-edge,
unisce due vertici grigi).
u
v
c
Ordinamento Topologico
Ingresso: un grafo orientato e aciclico (DAG: Direct
Acyclic Graph)
Uscita: una lista ordinata e lineare dei vertici di G
<u1, u2, …, u|V|> tale che se G contiene l’arco orientato (u,v)
allora nell’ordinamento u precede v.
2
1
2
3
3
4
4
1
3
1
4
3
oppure
2
4
1
oppure
2
Ordinamento Topologico
TOPOLOGICAL-SORT(G)
1.
chiama DFS(G) per calcolare I tempi di fine visita f[v] per ogni
vertice v
2.
appena la visita è finita inseriscilo in testa ad una lista concatenata
3.
restituisci la lista concatenata dei vertici
f[2] > f[1] > f[3] > f[4]
2
1
3
4
DFS(G) richiede tempo Θ(|V| + |E|).
L’inserimento di ognuno dei |V| vertici nella lista concatenata
richiede tempo O(1).
Quindi, si può eseguire un ordinamento topologico in
tempo Θ(|V| + |E|).
Ordinamento Topologico
Proposizione
TOPOLOGICAL-SORT(G) produce un ordinamento
topologico di un grafo orientato aciclico G.
Dimostrazione
Basta dimostrare che se G è aciclico, allora per ogni arco
(u,v) in E si ha che f[u] > f[v].
Essendo aciclico, non esistono archi grigi (Back-edge).
Allora (u,v) è bianco oppure nero.
• Se (u,v) è bianco allora f[u] > f[v] per il teorema delle
parentesi.
• Se (u,v) è nero allora f[u] > f[v] perché v è già stato
visitato prima di finire la visita in u.