APA I e II 21 Gli algoritmi di visita dei grafi
1
Gli algoritmi di visita dei grafi
Gianpiero Cabodi e Paolo CamuratiDip. Automatica e Informatica
Politecnico di Torino
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 2
Algoritmi di visita
Visita di un grafo G=(V, E):a partire da un vertice dato, seguendo gliarchi con una certa strategia, elencare i vertici incontrati, eventualmenteaggiungendo altre informazioni.
Algoritmi:in profondità (depth-first search, DFS)in ampiezza (breadth-first search, BFS).
APA I e II 21 Gli algoritmi di visita dei grafi
2
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 3
Visita in profonditàA partire da un vertice s:
visita tutti i vertici del grafo (raggiungibili da s e non)
etichetta ogni vertice v con tempo di scoperta/ tempo di fine elaborazione pre[v]/post[v]
etichetta ogni arco:grafi orientati: T(ree), B(ackward), F(orward), C(ross)grafi non orientati: T(ree), B(ackward)
genera una foresta di alberi della visita in profondità.
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 4
Principi base
Profondità: espande l’ultimo vertice scopertoche ha ancora vertici non ancora scopertiadiacenti.Scoperta di un vertice: prima volta che si incontra nella visita (discesa ricorsiva).Completamento: fine dell’elaborazione del vertice (uscita dalla ricorsione).Scoperta/Completamento: tempo discreto che avanza mediante contatore time.
APA I e II 21 Gli algoritmi di visita dei grafi
3
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 5
I vertici si distinguono (concettualmente) in:bianchi: non ancora scopertigrigi: scoperti, ma non completatineri: scoperti e completati.
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 6
Classificazione degli archiGrafo orientato:
T: archi dell'albero della visita in profonditàB: connettono un vertice u ad un suo antenato v nell’albero: pre(v)<pre(u) e post(v)>post(u)F: connettono un vertice u ad un suo discendente v nell’albero: pre(v)>pre(u) e post(v)<post(u)C: archi rimanenti.
Grafo non orientato: solo archi T e B.
APA I e II 21 Gli algoritmi di visita dei grafi
4
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 7
Strutture dati
grafo come lista delle adiacenzevettore pre dei tempi di scopertavettore post dei tempi di completamentopossibilità di gestire il vettore π dei predecessori per la costruzione della foresta degli alberi di visita in profonditàetichette degli archi T, B, F, C.
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 8
Algoritmo
static int time, pre[maxV], post[maxV];void GRAPHsearch(Graph G){ int v;time = 0;for (v=0; v < G->V; v++){pre[v] = -1;post[v] = -1;
}for (v=0; v < G->V; v++)if (pre[v]== -1)dfsR(G, EDGE(v,v));
}
APA I e II 21 Gli algoritmi di visita dei grafi
5
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 9
dfsR con lista adiacenzevoid dfsR(Graph G, Edge e){ link t; int i, v, w = e.w; Edge x;show("tree" , e) ;pre[w] = time++;for (t = G->adj[w]; t != NULL; t = t->next)if (pre[t->v] == -1)dfsR(G, EDGE(w, t->v));
else{ v = t->v; x = EDGE(w, v);if (post[v] == -1) show("back", x);else if(pre[v]>pre[w]) show("down", x)else show("cross", x) ;
}post[w] = time++;
}
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 10
Esempioπ
r s t
v w x
time = -1
APA I e II 21 Gli algoritmi di visita dei grafi
6
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 11
π
r s t
v w x
0/
time = 0r
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 12
π
r s t
v w x
0/
time = 1r
1/
s
APA I e II 21 Gli algoritmi di visita dei grafi
7
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 13
π
r s t
v w x
0/
time = 2r
1/
s
2/
w
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 14
π
r s t
v w x
0/
time = 3r
1/
s
2/3
w
APA I e II 21 Gli algoritmi di visita dei grafi
8
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 15
π
r s t
v w x
0/
time = 4r
1/4
s
2/3
w
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 16
π
r s t
v w x
0/
time = 5r
1/4
s
2/3
w
5/
v
APA I e II 21 Gli algoritmi di visita dei grafi
9
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 17
π
r s t
v w x
0/
time = 6r
1/4
s
2/3
w
5/6
v
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 18
π
r s t
v w x
0/7
time = 7r
1/4
s
2/3
w
5/6
v
APA I e II 21 Gli algoritmi di visita dei grafi
10
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 19
π
r s t
v w x
0/7
time = 8r
1/4
s
2/3
w
5/6
v
8/
t
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 20
π
r s t
v w x
0/7
time = 9r
1/4
s
2/3
w
5/6
v
8/
t
x
9/
APA I e II 21 Gli algoritmi di visita dei grafi
11
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 21
π
r s t
v w x
0/7
time = 10r
1/4
s
2/3
w
5/6
v
8/
t
x
9/10
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 22
π
r s t
v w x
0/7
time = 11r
1/4
s
2/3
w
5/6
v
8/11
t
x
9/10
APA I e II 21 Gli algoritmi di visita dei grafi
12
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 23
Complessità (lista adiacenze)
Inizializzazionevisita ricorsiva da uT(n) = Θ(|V|+|E|). Con la matrice delle adiacenze: T(n) = Θ(|V|2).
Θ(|V|)
Θ(|E|)
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 24
Esempio
b a s e
c d f gb a s e
c d f g
2/5
3/4 6/7
1/8 0/9
11/12
10/15
13/14
T
C
B T TT
T
C C
T
C BF
APA I e II 21 Gli algoritmi di visita dei grafi
13
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 25
s
a
b
c
d
e
f g
T
T
T
T
T T
B
B
C
C
C
C
F
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 26
Visita in ampiezza
A partire da un vertice s:determina tutti i vertici raggiungibili da scalcola la distanza minima da s di tutti i
vertici da esso raggiungibili.genera un albero della visita in ampiezza.
Ampiezza: espande tutta la frontiera travertici già scoperti/non ancora scoperti.
APA I e II 21 Gli algoritmi di visita dei grafi
14
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 27
Principi base
Scoperta di un vertice: prima volta che si incontra nella visita.Vertici:
bianchi: non ancora scopertigrigi: scoperti, ma non completatineri: scoperti e completati.
Dato vertice u:pre[u] = distanza di u da sst[u]: padre di u nell’albero della visita.
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 28
Strutture dati
grafo come matrice delle adiacenzecoda Q dei vertici grigivettore st dei predecessorivettore pre delle distanze minime.
APA I e II 21 Gli algoritmi di visita dei grafi
15
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 29
Algoritmo (matrice delle adiacenze)}void bfs(Graph G, Edge e){ int v, w; int flag=0;QUEUEput(e); while (!QUEUEempty())if (pre[(e = QUEUEget()).w] == -1)
{
pre[e.w] = flag ? pre[e.v]+1:0;
flag=1;
st[e.w] = e.v;for (v = 0; v < G->V; v++)if (G->adj[e.w][v] == 1)if (pre[v] == -1)QUEUEput(EDGE(e.w, v));
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 30
Esempio
r s t u
v w x y
Q st
APA I e II 21 Gli algoritmi di visita dei grafi
16
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 31
r s t u
v w x y
∞
∞
∞∞
∞∞ ∞
0
ssQ st
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 32
r s t u
v w x y
1
∞
∞∞
1∞ ∞
0
srQ w
r w
st
APA I e II 21 Gli algoritmi di visita dei grafi
17
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 33
r s t u
v w x y
1
∞
∞∞
12 ∞
0
swQ v
r w
v
st
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 34
r s t u
v w x y
1
2
∞2
12 ∞
0
svQ t
r w
v
x
t x
st
APA I e II 21 Gli algoritmi di visita dei grafi
18
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 35
r s t u
w x y
1
2
∞2
12 ∞
0
stQ x
r w
v t x
st
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 36
r s t u
w x y
1
2
32
12 ∞
0
sxQ u
r w
v t x
u
st
APA I e II 21 Gli algoritmi di visita dei grafi
19
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 37
r s t u
w x y
1
2
32
12 3
0
suQ y
r w
v t x
u y
st
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 38
r s t u
w x y
1
2
32
12 3
0
syQ
r w
v t x
u y
st
APA I e II 21 Gli algoritmi di visita dei grafi
20
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 39
r s t u
w x y
1
2
32
12 3
0
sQ
r w
v t x
u y
st
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 40
Complessità
Operazioni sulla codaScansione della matrice delle adiacenze T(n) = Θ(|V|2).Con la lista delle adiacenze: T(n) = O(|V|+|E|).
APA I e II 21 Gli algoritmi di visita dei grafi
21
A.A. 2004/2005 21 Gli algoritmi di visita dei grafi 41
Proprietà
Cammini minimi: la visita in ampiezza determina la minima distanza tra s e ogni vertice raggiungibile da esso.
s
r w
v t x
u y
st
Cammino minimo da s a u:s, w, t, ulunghezza = 3