21 Gli algoritmi di visita dei grafi -...

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).


2


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à.


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.


3


I vertici si distinguono (concettualmente) in:bianchi: non ancora scopertigrigi: scoperti, ma non completatineri: scoperti e completati.


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.


4


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.


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));

}


5


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++;

}


Esempioπ

r s t

v w x

time = -1


6


π

r s t

v w x

0/

time = 0r


π

r s t

v w x

0/

time = 1r

1/

s


7


π

r s t

v w x

0/

time = 2r

1/

s

2/

w


π

r s t

v w x

0/

time = 3r

1/

s

2/3

w


8


π

r s t

v w x

0/

time = 4r

1/4

s

2/3

w


π

r s t

v w x

0/

time = 5r

1/4

s

2/3

w

5/

v


9


π

r s t

v w x

0/

time = 6r

1/4

s

2/3

w

5/6

v


π

r s t

v w x

0/7

time = 7r

1/4

s

2/3

w

5/6

v


10


π

r s t

v w x

0/7

time = 8r

1/4

s

2/3

w

5/6

v

8/

t


π

r s t

v w x

0/7

time = 9r

1/4

s

2/3

w

5/6

v

8/

t

x

9/


11


π

r s t

v w x

0/7

time = 10r

1/4

s

2/3

w

5/6

v

8/

t

x

9/10


π

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


12


Complessità (lista adiacenze)

Inizializzazionevisita ricorsiva da uT(n) = Θ(|V|+|E|). Con la matrice delle adiacenze: T(n) = Θ(|V|2).

Θ(|V|)

Θ(|E|)


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


13


s

a

b

c

d

e

f g

T

T

T

T

T T

B

B

C

C

C

C

F


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.


14


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.


Strutture dati

grafo come matrice delle adiacenzecoda Q dei vertici grigivettore st dei predecessorivettore pre delle distanze minime.


15


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));


Esempio

r s t u

v w x y

Q st


16


r s t u

v w x y

∞

∞

∞∞

∞∞ ∞

0

ssQ st


r s t u

v w x y

1

∞

∞∞

1∞ ∞

0

srQ w

r w

st


17


r s t u

v w x y

1

∞

∞∞

12 ∞

0

swQ v

r w

v

st


r s t u

v w x y

1

2

∞2

12 ∞

0

svQ t

r w

v

x

t x

st


18


r s t u

w x y

1

2

∞2

12 ∞

0

stQ x

r w

v t x

st


r s t u

w x y

1

2

32

12 ∞

0

sxQ u

r w

v t x

u

st


19


r s t u

w x y

1

2

32

12 3

0

suQ y

r w

v t x

u y

st


r s t u

w x y

1

2

32

12 3

0

syQ

r w

v t x

u y

st


20


r s t u

w x y

1

2

32

12 3

0

sQ

r w

v t x

u y

st


Complessità

Operazioni sulla codaScansione della matrice delle adiacenze T(n) = Θ(|V|2).Con la lista delle adiacenze: T(n) = O(|V|+|E|).


21


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

21 Gli algoritmi di visita dei grafi -...

Documents

Transcript of 21 Gli algoritmi di visita dei grafi -...