Algoritmi di visita
Scopo: visitare tutti i vertici di un grafo per scoprirne proprietà
di vario tipo. Alcune applicazioni degli algoritmi di visita:
• scoprire tutti i vertici raggiungibili da un determinato vertice
• verificare se il grafo contiene cicli
• verificare se un grafo è (fortemente) connesso
• quali sono le componenti (fortemente) connesse di un grafo
• se un grafo non orientato è bipartito (cioè se è possibile
suddividere i vertici in due classi tali che non ci siano archi che
collegano vertici che stanno nella medesima classe)
• ordinamento totale dei vertici in un DAG che rispetti i vincoli di
precedenza (ordinamento topologico)
Master Bioinformatica 2002: Visite di Grafi
Due tipi di visita
Cominciando a esplorare il grafo a partire una
sorgente, intuitivamente:
• Visita in ampiezza: si scoprono prima tutti i
vertici che sono a distanza n (numero di archi) dalla
sorgente prima di scoprire quelli che sono a distanza
n+1
• Visita in profondità: si scoprono sempre prima gli
adiacenti dell’ultimo adiacente scoperto prima di
scoprire tutti gli altri
Master Bioinformatica 2002: Visite di Grafi
1
4
a
d
3 c
b
2
6
7
e
f
9
5
g
h
i
8
Possibile ordine di visita scoperto dalla visita in ampiezza
a, d, c, b, g, f, e, i, h
Master Bioinformatica 2002: Visite di Grafi
1
2
a
d
9 c
b
7
6
3
e
f
4
8
g
h
i
5
Possibile ordine di visita scoperto dalla visita in profondità
a, b, e, h, i, f, d, g, c
Master Bioinformatica 2002: Visite di Grafi
Algoritmi di visita
Possono essere visti come realizzazioni di un unico algoritmo
astratto. Dividiamo l’insieme dei vertici in tre insiemi
colorati in modo diverso
Bianco:
Vertici non ancora visitati o “scoperti”
Grigio:
Vertici visitati i cui adiacenti non sono ancora stati tutti
scoperti, quindi vertici utili per continuare la visita
Nero:
Vertici visitati e non più utili per continuare a scoprire
altri vertici (i loro adiacenti sono stati tutti già scoperti)
Master Bioinformatica 2002: Visite di Grafi
INIZIALIZZA (G)
for ogni u  V do
color u  white
Complessità: O (V)
VISITA (G, s)
color s  gray
while ci sono vertici grigi do
u  un vertice grigio
if c’è v bianco adiacente a u
then color v  gray
else color u  black
Complessità O(V+E) se si scandiscono gli adiacenti di un
vertice una volta sola
Master Bioinformatica 2002: Visite di Grafi
Proprietà 1: Il colore di un vertice può solo passare da
“white” a “gray” a “black”.
Invarianti del while:
INV1: Se (u,v)  E[G] e u è nero, allora v è o grigio o nero.
INV2: Tutti i vertici grigi o neri sono raggiungibili da s.
INV3: Qualunque cammino da s a un vertice bianco deve contenere
almeno un vertice grigio.
Dimostrazione.
Se s è grigio: vero.
Se s è nero: se non ci fosse nessun vertice grigio ci sarebbe un
vertice bianco adiacente ad uno nero, che è impossibile per
l'invariante INV1.
Master Bioinformatica 2002: Visite di Grafi
Teorema.
Al termine dell'algoritmo di visita, un vertice è nero se e solo se è
raggiungibile da s.
Dimostrazione.
() Per INV2 all'uscita del while tutti i vertici neri sono
raggiungibili da s.
() Da INV3 e dalla condizione di uscita del ciclo
(non ci sono vertici grigi) si ricava che non ci può
essere nessun vertice bianco raggiungibile da s.
Master Bioinformatica 2002: Visite di Grafi
L’algoritmo può essere modificato in modo da ricordare, per ogni
vertice che viene scoperto, quale vertice grigio ha permesso di
visitarlo, ossia ricordare l’arco percorso.
Ad ogni vertice u si associa un attributo P[u] che rappresenta il
vertice (predecessore) che ha permesso di scoprirlo.
L’algoritmo di inizializzazione deve essere esteso per
inizializzare P:
INIZIALIZZA (G)
for ogni vertice u  V[G] do
color [u]  white
P[u]  NULL
Master Bioinformatica 2002: Visite di Grafi
VISITA (G, s)
color [s]  gray
while ci sono vertici grigi do
scegli un vertice grigio u
if esiste un vertice bianco v adiacente a u
then color [v]  gray
P[v]  u
else color [u]  black
Proprietà 2: Al termine dell'esecuzione di VISITA (G,s) tutti e
soli i vertici neri diversi da s hanno un predecessore
diverso da NULL.
Master Bioinformatica 2002: Visite di Grafi
Sottografo dei predecessori GP =(VP, EP):
VP = {v  V: P [v]  NULL}  {s}
EP = {(P[v], v)  E: v  VP -{s}}
Come conseguenza immediata della Proprietà 2, al termine
dell'esecuzione di VISITA (G,s) VP è l'insieme di tutti i
vertici neri, cioè di tutti i vertici raggiungibili da s.
Teorema. Il sottografo dei predecessori costruito
dall'algoritmo di visita è un albero.
Dimostrazione.
Basta dimostrare che è invariante del while la seguente
proprietà: <VP, EP> è connesso e |EP| = |VP| - 1.
Master Bioinformatica 2002: Visite di Grafi
In certe applicazioni può essere necessario visitare tutti i vertici di
un grafo. Questo può essere fatto nel modo seguente:
VISITA_TUTTI_I_VERTICI (G)
INIZIALIZZA (G)
for ogni u  V do
if color u = white
then VISITA (G, u)
Master Bioinformatica 2002: Visite di Grafi
Per gestire l'insieme dei vertici grigi in modo efficiente, si può
utilizzare una struttura dati D i cui elementi siano ordinati, e su cui
sono definite le operazioni:
make_empty
crea una struttura vuota
first (D)
restituisce il primo elemento di D (senza
modificare D)
add (D, x)
aggiunge l'elemento x a D
remove-first (D) toglie da D il primo elemento
not_empty (D)
restituisce true se D non è vuota e false
altrimenti
•Se add (D,x) aggiunge x come ultimo elemento di D, D è una
CODA.
•Se add (D,x) aggiunge x come primo elemento di D, D è una
PILA (STACK);
Master Bioinformatica 2002: Visite di Grafi
L'algoritmo diventa:
VISITA (G, s)
D  make_empty
color s  gray
add (D, s)
while not_empty (D) do
u  first (D)
if c’è v bianco adiacente a u
then color v  gray
add (D, v)
else color u  black
remove_first (D)
Master Bioinformatica 2002: Visite di Grafi
Visita in ampiezza
Breadth-First-Search (BFS)
La struttura dati D è una CODA
Master Bioinformatica 2002: Visite di Grafi
B
A
F
C
E
G
A
B
D
Q
H
A B D
head
Master Bioinformatica 2002: Visite di Grafi
D
B
A
F
C
E
G
A
B
D
Q
H
B D C F
head
Master Bioinformatica 2002: Visite di Grafi
C
D
F
B
A
F
C
E
G
A
B
D
Q
H
D C F H
head
Master Bioinformatica 2002: Visite di Grafi
C
D
F
H
B
A
F
C
E
G
A
B
D
Q
H
C F H E
head
Master Bioinformatica 2002: Visite di Grafi
C
E
D
F
H
B
A
F
C
E
G
A
B
D
Q
H
F H E G
head
Master Bioinformatica 2002: Visite di Grafi
D
C
F
E
G
H
B
A
F
C
E
G
A
B
D
Q
H
H E G
head
Master Bioinformatica 2002: Visite di Grafi
D
C
F
E
G
H
B
A
F
C
E
G
A
B
D
Q
H
E G
head
Master Bioinformatica 2002: Visite di Grafi
D
C
F
E
G
H
B
A
F
C
E
G
A
B
D
Q
H
G
head
Master Bioinformatica 2002: Visite di Grafi
D
C
F
E
G
H
B
A
F
C
E
G
A
B
D
H
Q
head
Master Bioinformatica 2002: Visite di Grafi
D
C
F
E
G
H
BFS-VISITA (G, s)
Q  make_empty
color s  gray
enqueue (Q, s)
while not_empty (Q) do
u  head (Q)
if c’è v bianco adiacente a u
then color v  gray
P[v  u
enqueue (Q, v)
else color u  black
dequeue (Q)
Poichè la head della coda non
cambia finché ci sono adiacenti
bianchi, l'algoritmo può essere
modificato nel modo seguente:
while c’è un v adiacente a u
non considerato do
if color v = white
then color v  gray
P[v  u
enqueue (Q, v)
color u  black
dequeue (Q)
Master Bioinformatica 2002: Visite di Grafi
N.B. Nella visita in ampiezza Breadth First Search
l’albero viene costruito a livelli
A
B
D
C
F
E
G
H
Possiamo riscrivere l’algoritmo associando ad ogni vertice ‘v’ un
attributo ‘d[v]’, che ricorda il suo livello nell’albero ottenuto con
la visita.
Master Bioinformatica 2002: Visite di Grafi
Inizializzazione per il calcolo delle distanze
INIZIALIZZA (G)
for ogni u  V do
color u  white
P[u  NULL
du  
Master Bioinformatica 2002: Visite di Grafi
BFS-VISITA (G, s)
Q  make_empty
color s  gray
d[s]  0
enqueue (Q, s)
while not_empty (Q) do
u  head (Q)
while c’è v adiacente a u
non considerato do
if color v = white
then color v  gray
P[v  u
dv  d[u] + 1
enqueue (Q, v)
color u  black
dequeue (Q)
Master Bioinformatica 2002: Visite di Grafi
Liste di adiacenza in ordine alfabetico
A
B
D
B
A
C
C
D
E
B
E
A
H
F
G
B
H
D
F
C
G
F
Master Bioinformatica 2002: Visite di Grafi
Liste di adiacenza in ordine alfabetico inverso
A
D
B
B
F
C
C
D
E
E
B
H
A
F
G
G
H
D
A
C
B
F
Master Bioinformatica 2002: Visite di Grafi
B
F
C
A
E
G
H
D
Vertici memorizzati nelle liste
Vertici memorizzati nelle liste
di adiacenza in ordine inverso
di adiacenza in ordine alfabetico
A
B
A
D
C
F
E
G
B
D
H
C
H
G
E
Master Bioinformatica 2002: Visite di Grafi
F
A
A
B
D
D
C
F
E
G
G
H
C
H
G
B
F
E
Teorema
Al termine di una BFS-VISITA si ha: vV[G] : d[v] = (s, v).
(s, v) indica la distanza di v dal vertice sorgente (lunghezza di un
cammino minimo da s a v).
Master Bioinformatica 2002: Visite di Grafi
Proprietà 4
• In Q ci sono tutti e soli i vertici grigi
• Se <v1, v2, . . . , vn> è il contenuto di Q, allora:
d[vn]  d[v1] + 1
d[vi]  d[vi+1]
1  i  n-1
Lemma
La seguente proprietà è un invariante dei due while di BFS-VISITA:
d[v] = (s,v) per tutti i vertici v grigi o neri.
Dimostrazione
È sufficiente dimostrare che l’assegnazione d[v]  d[u] + 1 rende
d[v] = (s,v); la dimostrazione del lemma è una ovvia conseguenza
di questo fatto.
Master Bioinformatica 2002: Visite di Grafi
Consideriamo in G un cammino minimo da s a v.
Per l’invariante INV3 tale cammino contiene almeno un
vertice t grigio. Il cammino minimo può allora essere visto
come concatenazione dei due cammini minimi da s a t e da t a v.
(s,v) = (s,t) + (t,v)  (s,t) + 1
((t,v)  1 poichè t  v).
Ma il vertice t è in Q (t è grigio) e per la Proprietà 4, essendo
u = head(Q): d[u]  d[t] = (s,t).
Si ottiene pertanto: (s,v)  (s,t) + 1 = d[t] + 1  d[u] + 1.
Poichè s
u  v è un cammino in G da s a v, esso non può avere
lunghezza minore di quella di un cammino minimo, allora
(s,v) = d[u] + 1 e l’assegnazione d[v]  d[u] + 1 rende
d[v] = (s,v).
Master Bioinformatica 2002: Visite di Grafi
Teorema.
Al termine dell'esecuzione di BFS si ha d[v] = (s,v) per tutti i
vertici v  V.
Dimostrazione.
Se v non è raggiungible da s allora d[v] rimane  = (s,v).
Altrimenti v è nero e il teorema vale per il Lemma precedente.
• per ogni vertice v raggiungibile da s, il cammino da s a v
sull’albero ottenuto con la visita è un cammino minimo.
• Il livello di un vertice nell’albero è indipendente dall’ordine
in cui sono memorizzati i vertici nelle liste di adiacenza.
Master Bioinformatica 2002: Visite di Grafi