Breath-first search
Visita in ampiezza di un grafo
Algoritmo
Esempio
Complessità dell’algoritmo
Proprietà
Albero BFS
Breath-first search
Dato un grafo G=(V,E) e un specifico vertice s chiamato
sorgente, la visita in ampiezza (in inglese breath-first
search) esplora sistematicamente gli archi di G per
scoprire ogni vertice che sia raggiungibile da s.
Essa calcola la distanza (ossia il numero minimo di
archi) da s ad ogni vertice raggiungibile.
Inoltre, produce un “albero BFS” che ha come radice s
e comprende tutti vertici raggiungibili.
Nell’albero BFS il cammino da s a v corrisponde ad un
“cammino minimo”.
L’algoritmo funziona per grafi orientati e non orientati.
Breath-first search
Strutture dati utilizzate:
• Liste di adiacenza Adj: per conoscere i vertici
adiacenti a un vertice.
• color[u]: per colora il vertice u di bianco (vertice non
scoperto), di grigio (vertice appena scoperto) e di nero
(vertice non più sulla frontiera dei vertici appena
scoperti).
• d[u]: la distanza di u. All’inizio è ∞.
• p[u]: il predecessore di u nell’albero BFS.
Algoritmo
BFS(G,s)
1.
for ogni vertice u in V[G] – {s}
2.
do color[u] ← WHITE
3.
d[u] ← ∞
4.
p[u] ← NIL
5.
colors[s] ← GRAY
6.
d[s] ← 0
7.
p[s] ← NIL
8.
Q ← {s}
// inizializzazione di ogni vertice
// si comincia dal vertice s
// coda dei vertici grigi sulla
frontiera
All’inizio tutti i vertici sono bianchi e, successivamente,
possono diventare grigi e poi neri.
La visita in ampiezza costruisce un albero BFS che
all’inizio contiene solo la radice: il vertice sorgente s.
Algortimo
9.
10.
11.
12.
13.
14.
15.
16.
17.
18.
while Q ≠Ø
do u ← head[Q]
// termina quando la coda è
vuota
// prendi prossimo elemento
dalla coda
// scopri vertici bianchi adiacenti
for ogni vertice v in Adj[u]
do if color[v] = WHITE
then color[v] ← GRAY // diventano grigi
d[v] ← d[u] + 1
// la distanza è d[u] +1
p[v] ← u
// il predecessore è u
ENQUEUE(Q,v)
// e vanno in Q
DEQUEUE(Q)
color[u] ← BLACK
// u nero: non più sulla frontiera
Un vertice viene scoperto, la prima volta che viene
incontrato durante la visita: in tale istante esso cessa di
essere bianco.
Esempio
r
s
t
u
∞
0
∞
∞
(a)
Q = {s}
d[s] = 0
r
s
t
1
0
∞
Q = {w, r}
∞ d[w] = 1
d[r] = 1
(b)
u
∞
∞
∞
∞
∞
1
∞
∞
v
w
x
y
v
w
x
y
r
s
t
u
r
s
t
u
1
0
2
∞
1
0
2
∞
2
1
2
∞
v
w
x
y
(c)
∞
1
2
∞
v
w
x
y
Q = {r, t, x}
d[r] = 1
d[t] = 2
d[x] = 2
(d)
Q = {t, x, v}
d[t] = 2
d[x] = 2
d[v] = 2
Esempio
r
s
t
u
1
0
2
3
(d)
2
1
2
∞
v
w
x
y
r
s
t
u
1
0
2
3
(f)
2
1
2
3
v
w
x
y
r
s
t
u
1
0
2
3
2
1
2
3
v
w
x
y
(h)
Q = {x, v, u}
d[x] = 2
d[v] = 2
d[u] = 3
Q=Ø
s
t
u
1
0
2
3
2
1
2
3
v
w
x
y
r
s
t
u
1
0
2
3
(e)
Q = {u, y}
d[u] = 3
d[y] = 3
r
(g)
Q = {v, u, y}
d[v] = 2
d[u] = 3
d[y] = 3
Q = {y}
d[y] = 3
2
1
2
3
v
w
x
y
Complessità
Analisi del tempo di esecuzione su un grafo G=(V,E):
• Il tempo necessario per l’inizializzazione è O(|V|), tempo
O(1) per ogni vertice.
• Le operazioni di inserimento e rimozione dalla coda è
O(1), quindi il tempo totale dedicato alle operazioni sulla
coda è O(|V|) (ogni vertice diventa grigio solo una volta).
• La lista di adiacenza di ogni vertice viene scandita solo
quando il vertice è estratto dalla coda, ossia al massimo
una volta sola.
• Le somma di tutte le liste di adiacenza è pari a Θ(|E|).
• Sommando il tempo di inizializzazione e il tempo per
visitare i vertici, si ha che l’algoritmo di BFS() viene
eseguito in tempo O(|V| + |E|).
Cammino minimo
Si definisce la distanza minima δ(s,v) ≥ 0 da s a v come il
numero minimo di archi di un cammino dal vertice s al
vertice v, oppure δ(s,v) = ∞ se non esiste nessun cammino
da s a v.
Quando δ(s,v) = ∞, v risulta irraggiungibile partendo da s.
Un cammino di lunghezza δ(s,v) da s a v è chiamato
cammino minimo da s a v.
Si ha la seguente proprietà:
Per ogni arco (u,v) in E, δ(s,v) ≤ δ(s,u) +1.
Nodi in coda
Proposizione
I nodi che entrano in Q sono tutti e soli i nodi u con
δ(s,u) < ∞, ossia tutti i nodi raggiungibili da
s.
Dimostrazione
“Se il nodo v entra in Q allora δ(s,v) < ∞.”
Per induzione sull’i-esima iterazione di ENQUEUE().
Per i = 0, δ(s,s) = 0 < ∞.
Supponiamo vero per k<i. Se v viene messo in coda, allora
si ha che esiste un nodo u in coda tale che v appartiene a
Adj[u].
Nodi in coda
Si ha che per ipotesi induttiva δ(s,u) = k < ∞ e, inoltre, esiste
l’arco (u,v). Quindi
δ(s,v) ≤ δ(s,u) +1 < ∞.
“Se δ(s,v) < ∞ allora il nodo v entra in Q.”
Per induzione su δ(s,v) = i.
Per δ(s,v) = 0, è vero solo per v = s.
Si ha che se δ(s,u) = i-1, allora u entra in coda per ipotesi
induttiva.
δ(s,v) < ∞, quindi esiste un cammino minimo da s a v.
Nodi in coda
Esiste un cammino <v0, …, vi-1, vi>, con v0= s e vi = v.
Si ha che δ(s, vi-1) = i-1. vi-1 entra in coda per ipotesi
induttiva. Quindi quando verrà visitato la lista di adiacenza
di vi-1 :
a) v è bianco e verrà messo in coda
b) v è già stato messo in coda
Corollario
Se il grafo è connesso (o fortemente connesso nel caso
di grafo orientato) allora tutti i nodi vengono messi in
coda.
Proprietà
Proposizione
Per ogni i≥1, all’inizio dell’i-esima iterazione del ciclo
while si ha:
a) Per ogni vn nero, vg grigio, vb bianco
δ(s, vn) ≤ δ(s, vg) ≤ δ(s, vb)
b) Per ogni nodo v nella coda d[v]=δ(s, v)
c) Se la coda Q contiene i vertici {v1, v2,… ,vr} dove v1 è la
testa della coda e vr è il fondo. Allora d[vr] ≤ d[v1] + 1 e
d[vi] ≤ d[vi+1] per i=1, 2,… ,r-1
Proprietà
Dimostrazione
Si dimostra per induzione sui cicli while i.
Per i = 1, base induttiva, si ha:
a) L’unico nodo grigio è s, tutti gli altri sono bianchi.
Per ogni v in V - {s}, δ(s, v) > 0 = δ(s, s).
b) d[s] = 0 = δ(s, s).
c) Q contiene solo s quindi la verifica è immediata.
Proprietà
Per i > 1 si ha che le preposizioni a), b) e c) verificate per
i-1, per ipotesi induttiva.
Verifichiamo a)
Durante l’iterazione dell’i-1 ciclo per arrivare all’inizio del
i-esimo ciclo si ha che:
-ui-1: grigio → nero
-per ogni v in Adj[ui-1] e bianco: bianco → grigio
Tutte le altre relazioni risultano invariate. Quindi, vanno
verificate le condizioni per i nodi che hanno cambiato colore.
Per quanato riguarda δ(s, ui-1) si ha che per ipotesi induttiva
b) è minore a tutti i bianchi, compresi quelli (v in Adj[ui-1] e
bianchi) diventati grigi dopo l’iterazione i-1.
Proprietà
Inoltre, poiché ui-1 era all’inizio della coda e per ipotesi
induttiva c) e a), δ(s, ui-1) è minore di tutti i grigi presenti
nella coda all’inizio dell’i-1 ciclo.
Per quanto riguarda ogni v in Adj[ui-1] e bianco, supponiamo
per assurdo che esista un bianco w tale che
δ(s, w) < δ(s, v). Allora δ(s, w) ≤ δ(s, ui-1).
Nel cammino minimo tra s e w, ci sarà x in Adj[w] tale che
δ(s, x) < δ(s, w) ≤ δ(s, ui-1). x non può essere grigio per
ipotesi c) e perché ui-1 era all’inizio della coda. Quindi x è
nero, ma w bianco è in Adj[x] ed x è nero. Assurdo, sono già
stati visitati tutti gli elementi di Adj[x].
Proprietà
Per i > 1 si ha che le preposizioni a), b) e c) verificate per
i-1, per ipotesi induttiva.
Verifichiamo b)
Durante l’iterazione dell’i-1 ciclo per arrivare all’inizio del iesimo ciclo si ha che:
ui-1 è all’inizio della coda e, quindi, d[ui-1] = δ(s, ui-1).
Per ogni v bianco in Adj[ui-1], v entra in coda e
d[v] = d[ui-1] + 1.
Se per assurdo d[v] ≠ δ(s, v), allora d[v] > δ(s, v) (esiste un
cammino meno distante tra s e v, meno lungo di quello che
passa per ui-1). Inoltre, si avrebbe δ(s, v) ≤ δ(s, ui-1).
Proprietà
Nel cammino minimo tra s e v, ci sarà x in Adj[v] tale che
δ(s, x) < δ(s, v) ≤ δ(s, ui-1). x non può essere grigio per
ipotesi c) e perché ui-1 era all’inizio della coda (infatti, δ(s, x)
risulta minore di tutti gli elementi nella coda, grigi).
Quindi x è nero, ma v bianco è in Adj[x] ed x è nero.
Assurdo, sono già stati visitati tutti gli elementi di Adj[x].
Proprietà
Per i > 1 si ha che le preposizioni a), b) e c) verificate per
i-1, per ipotesi induttiva.
Verifichiamo c)
Per arrivare all’inizio del i-esimo ciclo si ha che:
Viene rimosso v1 dalla testa della coda.
Se la coda risulta vuota la dimostrazione è immediata.
Altrimenti il nuovo elemento alla testa diventa v2. Si ha d[v1]
≤ d[v2] ≤ … ≤ d[vr] e d[vr] ≤ d[v1] +1.
Per ogni eventuale elemento aggiunto alla coda si ha
d[vr+k] = d[v1] + 1 ≤ d[v2] +1. Quindi, d[v2] ≤ … ≤ d[vr] ≤ d[vr+k]
e d[vr+k] ≤ d[v2] +1.
Albero BFS
Proposizione
Il vettore p definisce un sottografo di G, Tp=(Vp,Ep), dove:
Vp = {v in V: p[v] ≠ NIL}
Ep = {(p[v], v) in E: v in Vp - {s} }
Tp è un albero (albero BFS). Inoltre la lunghezza del
cammino tra s e u in Tp è δ(s,u).
Corollario
Se G è connesso (fortemente connesso nel caso di
grafo orientato) allora Tp è un albero di copertura
minima.
Albero BFS
Dimostrazione
Supponiamo Tp non sia un albero. Quindi esisterebbe un
ciclo <u0, u1, …, uk> con u0 = uk e k>1.
Per le preposizioni appena dimostrate. Si ha:
u0= p[u1], u1= p[u2], …, uk
e
d[u0], d[u1] = d[u0]+1, d[u2] = d[u1]+1, …, d[uk] = d[uk-1]+1.
Ma allora d[u0] = d[uk] = d[u0] + k. Assurdo.
Inoltre, se p[v] ≠ NIL, allora v è entrato in coda ed è
raggiungibile da v. Il cammino da s a v determinato dal
vettore p è lungo d[v] = δ(s,v).