Breath-first search
Visita in ampiezza di un grafo
Algoritmo
Esempio
Complessità dell’algoritmo
Proprietà
Albero BFS
Grafo
Un grafo G = (V,E) consiste in:
- un insieme V di vertici (o nodi)
- un insieme E di coppie di vertici, detti archi: ogni arco
connette due vertici
Esempio 1: V = {persone che vivono in Italia}, E = {coppie
di persone che si sono strette la mano} [NON ORIENTATO]
Esempio 2: V = {persone che vivono in Italia},E = { (x,y)
tale che x ha inviato una mail a y} [ORIENTATO]
1
V= {1,2,3,4,5,6,7}
2
6
3
4
5
7
Scopo e tipi di visita di un grafo
Scopo: una visita (o attraversamento) di un grafo G
permette di esaminare i nodi e gli archi di G in modo
sistematico.
Problema di base in molte applicazioni.
Esistono varie tipologie di visite con diverse proprietà.
In particolare:
– visita in ampiezza (BFS = Breadth First Search)
– visita in profondità (DFS = Depth First Search)
Breath-first search
Dato un grafo G=(V,E) e un specifico vertice s chiamato
sorgente, la visita in ampiezza esplora gli archi di G
per scoprire ogni vertice che sia raggiungibile a partire
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
La visita in ampiezza esplora i nodi del grafo a partire
da quelli a distanza 1 da s. Dopo aver visitato i nodi a
distanza 1, visita quelli a distanza 2. E così via.
distanza=3
distanza=2
u
2
r
distanza=1
s
t
1
0
2
3
Cresce la
distanza dalla
sorgente
v
2
w
1
2
3
x
y
Archi dell’albero BFS
Via via visita
nodi più
distanti dalla
sorgente.
Struttura dati
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.
• Q: coda
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
// Q= 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
Visita della sorgente.
Stato iniziale: la sorgente è in Q.
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)
Terminata la visita dei
nodi a distanza 1.
Q = {t, x, v}
d[t] = 2
d[x] = 2
d[v] = 2
Terminata la visita dei
nodi a distanza 1.
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
Q = {x, v, u}
d[x] = 2
d[v] = 2
d[u] = 3
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)
Terminata la visita dei
nodi a distanza 2.
Terminata la visita del grafo G.
d[v] = 2
d[u] = 3
d[y] = 3
Q = {y}
d[y] = 3
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)
Terminata la visita dei nodi a
distanza 3.
Q = {v, u, y}
Q=Ø
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.
• Ogni nodo raggiungibile viene visitato 1 volta:
Le operazioni di inserimento e rimozione dalla coda è O(1),
quindi il tempo totale dedicato alle operazioni sulla coda è O(|V|).
Di ogni vertice scoperto viene visitata tutta la lista di
adiacenza, ossia quando il vertice è estratto dalla coda.
Si sommano le lunghezze delle liste di adiacenza dei nodi visitati.
Le somma delle liste di adiacenza di tutti i nodi è 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 per passare dal vertice s al vertice v.
Quando δ(s,v) = ∞, v risulta irraggiungibile partendo da s,
ossia non esiste alcun cammino da s a v.
Un cammino di lunghezza δ(s,v) da s a v è chiamato
cammino minimo da s a v. (Possono esserci più cammini minimi!)
Si ha la seguente proprietà:
Per ogni arco (u,v) in E, δ(s,v) ≤ δ(s,u) +1.
Nota: la visita BSF calcola la distanza minima di ogni
nodo raggiungibile dalla sorgente s.
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) < ∞.”
Si procede per induzione sull’i-esima iterazione
dell’operazione di ENQUEUE().
Per i = 0: nella coda si trova s δ(s,s) = 0 < ∞.
Per i > 0: Supponiamo vera la proposizione per ogni
iterazione k<i.
All’i-esima iterazione viene visitata la lista di adiacenza di un
Nodi in coda
I nodi bianchi v che vengono messi in coda appartengono
ad Adj[u].
Si ha che per ipotesi induttiva δ(s,u) < ∞ (u è stato inserito
alla k’-esima iterazione, k’ < i ) e, inoltre, esiste l’arco (u,v).
Quindi
δ(s,v) ≤ δ(s,u) +1 < ∞.
“Se δ(s,v) < ∞ allora il nodo v entra in Q.”
Si procede per induzione su δ(s,v) = i.
Per δ(s,v) = 0: è vero! v = s.
Per δ(s,v) = i>0: per ipotesi induttiva si ha che per ogni u
tale che δ(s,u) < i u è entrato in coda.
Nodi in coda
Sorgente
v0
vi-1
vi
Nodo v
δ(s,v) < ∞
δ(s,v) < ∞, quindi esiste un cammino minimo da s a v:
<v0, …, vi-1, vi>, con v0= s e vi = v.
Si ha che δ(s, vi-1) = i-1<i. vi-1 entra in coda per ipotesi
induttiva. Quindi, quando verrà visitata la lista di adiacenza
di vi-1, nella quale ci sarà anche vi = v, potrà verificarsi:
a) v è bianco e verrà messo in coda
b) v è grigio o nero e quindi è 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.
Albero BFS
Proposizione
Il vettore p definisce un sottografo di G, Tp=(Vp,Ep), dove:
Vp = {s e tutti 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 (minimum spanning tree),
ossia vengono selezionati il numero minimo di archi per cui il sottografo
risulta ancora connesso.
Albero BFS
Ecco l’albero BFS del grafo visto nell’esempio:
s
p(s)=NIL
0
Radice
p(r)=s
r
s
1
0
p(t)=w p(u)=t
t
u
2
r
1
w
3
v
2
1
2
3
v
w
x
y
p(v)=r
1
p(w)=s p(x)=w p(y)=x
2
x
y
2
2
3
3
t
u