Grafi: visita in profondita’

(1)

F. Damiani - Alg. & Lab. 04/05 (da M. Zacchi - Alg. & Lab. 03/04)

Grafi: visita in profondita’

Una presentazione alternativa (con ulteriori dettagli)

………..

(2)

VISITA (G, s)

color [s] ← gray

while ci sono vertici grigi do u ← un vertice grigio

{if u non visitato then visitalo}

if c’è v bianco ∈ ADJ [u]

then color [v] ← gray π[v] ← u

else color [u] ← black

Consideriamo la versione “concreta” dell’algoritmo di visita generica con costruzione del sottografo dei predecessori:

D ← make_empty add (D, s)

first (D)

add (D, v) not empty(D)

(3)

La struttura dati D è uno STACK

Visita in profondità o Depth-First-Search (DFS)

(4)

B

D C

F

H E B

C D F E H

A C

G

D

H

E

F

A

Esempio

(5)

A B C D F G

H

A B C

D F E

H

A C D

H

F B

A B C D F E H

S

A C

G

D

H

E

F

Esempio

A C D

H

F B

A B C D F E H

S

A C

G

D

H

E

F

(6)

B

B C D F

A C

G

D

H

E

F

A B C D F G

H

A B C

D F E

H

Esempio

(7)

B

A B C D F

S

A C

G

D

H

E

F

A B C D F G

H

A B C

D F E

H

Esempio

(8)

B

A C

G

D

H

E

F

A B C D F G

H

A B C

D F E

H

Esempio

B C D F G

(9)

B

A B C D F

S

A C

G

D

H

E

F

A B C D F G

H

A B C

D F E

H

Esempio

G

(10)

B

B C D

A C

G

D

H

E

F

A B C D F G

H

A B C

D F E

H

Esempio

G F

(11)

B

A B C D S

A C

G

D

H

E

F

A B C D F G

H

A B C

D F E

H

Esempio

G

(12)

G B

C

B

A C

G

D

H

E

F

A B C D F G

H

A B C

D F E

H

Esempio

(13)

A S B

B

A C

G

D

H

E

F

A B C D F G

H

A B C

D F E

H

Esempio

G

(14)

A B C D F G

H

A B C

D F E

H B

A C

G

D

H

E

F

Esempio

G

(15)

S

A B C D F G

H

A B C

D F E

H B

A C

G

D

H

E

F

Esempio

G

(16)

1 2 3

4 5 6

7

8 A

B C D F G

H

A B C

D F E

H

Assumiamo che i vertici siano memorizzati nelle liste di adiacenza in ordine alfabetico.

B

A C

G

D

H

E

F 1

2

3 4

5

6 7

8

CONSIDERIAMO:

1. L’ORDINE IN CUI I VERTICI DIVENTANO GRIGI (cioe’ in cui sono visitati e in cui viene creato

il grafo dei pedecessori o albero di scoperta), E

8 7 6

5 4 2

1

3

2. L’ORDINE IN CUI DIVENTANO NERI Riprendiamo l’esempio (1/4)

G

(17)

B

A

C

G

D

H

E

F 1 8

2 7

3 6 4 5

5 4

6 2 7 1

8 3

A

B C D F E

H

G 16 15

14

13 12 9

8

11 1

2 3

4 5 6

7

10

Usando un unico contatore (che viene incrementato di 1 ogni volta che un vertice cambia colore) e

etichettando ogni vertice con i (due) valori assunti dal contatore subito dopo che il vertice ha cambiato colore si

ottengono i valori nel disegno a destra.

Invece, il disegno in basso riporta i valori assunti dai DUE contatori.

Riprendiamo l’esempio (2/4)

(18)

B

A C

G

D

H

E

F

Assumiamo ora che i vertici siano memorizzati nelle liste di adiacenza in ordine contrario.

A G F E H

D C 1

2 3 4 5 6

7 10

11 12 13

14 15 16

(19)

Si ottengono alberi diversi. Ci sono caratteristiche comuni ?

A G F E H

D C B 1

2 3 4 5 6 7

8 9

10 11 12 13 14 15 A 16

C D F E

H

G 16 15

14

13 12 9

8

11 1

2 3

4 5 6 10

7

B

(20)

L’albero viene creato dall’alto al basso: “in profondità”

La visita prende il nome di

“visita in profondità”:

Depth First Search

(21)

DFS-VISITA (G, s)

S ← make_empty_stack color [s] ← gray

push (S, s)

while not_empty (S) do u ← top (S)

{if u non ancora visitato then visitalo}

if c’è v bianco ∈ ADJ [u]

push (S, v)

else color [u] ← black pop (S)

for ogni v ∈ ADJ [u] do if color [v] = white

push (S, v) color [u] ← black

pop (S)

ATTENZIONE non funziona

Due versioni dell’algoritmo di visita in profondità (la seconda non funziona)

(22)

push (S, s)

while not_empty (S) do u ← top (S)

{if u non ancora visitato then visitalo}

push (S, v) color [u] ← black pop (s)

Se v è bianco diventa grigio e finisce sul top di S

La lista degli adiacenti da esaminare è quella del nuovo vertice sul top di S

Nella condizione invece la lista non è cambiata

Perché la seconda versione dell’algoritmo di visita in profondità non funziona?

(23)

push (S, s)

while not_empty (S) do u ← top (S)

{if top(S) non visitato then visitalo}

while c’e v ∈ ADJ [ top (S) ] non considerato do if color [v] = white

then color [v] ← gray π[v] ← top (S) push (S, v)

color [ top (S) ] ← black pop (S)

if color[v] = white

then color[v]← gray π[v] ← top(S) push (S, v) while Ptr[top(S)] ≠ nil do

Ptr[top (S)]←Ptr[top(S)].link v ← Ptr[top (S)].vtx

color[top(S)] ← black

Una seconda versione che funziona e una terza versione “ancora più concreta”

(24)

push (S, s)

while not_empty (S) do

if color [v] = white

then color [v] ← gray π[v] ← top (S) push (S, v)

while c’e’ v ∈ ADJ [top (S)] non considerato do

color[top(S)] ← black pop (S)

Si ottiene pertanto (seconda versione che funziona):

RICAPITOLANDO: la seconda versione che funziona

(25)

push (S, s)

while not_empty (S) do

if color [v] = white

then color [v]← gray π[v] ← top(S) push (S, v) while Ptr[top (S)] ≠ nil do

Ptr[top (S)] ← Ptr[top (S)].link v ← Ptr[top (S)].vtx

color[top(S)] ← black pop (S)

Si ottiene pertanto (terza versione “ancora più concreta”):

RICAPITOLANDO: la terza versione “ancora più concreta” (1/2)

(26)

Ovviamente il vettore Ptr dei puntatori alle liste di adiacenza dovrà essere inizializzato:

INIZIALIZZA (G) for ogni u ∈ V do

color [u] ← white π[u] ← nil

Ptr[u] ← ADJ[u]

RICAPITOLANDO: la terza versione “ancora più concreta” (2/2)

(27)

A D B

F

B C

A

E

D

F C

C A

D B

F

S

Ancora un esempio (1/7)

(28)

D

D B

F

B C

A

E

F

C A

D B

F

S

E

C E

(29)

D

A D B

F

B C

A

E

F C

C A

D B

F

S

E

C E E

(30)

D

D B

F

B C

A

E

F C

C A

D B

F

S

E

C E E F

(31)

F

B C

A

E

D

A

B F

C A

D

S

CE E F B

D

(32)

F

B C

A

E

D

B F

C A

D

S

CE E F B D

(33)

F

B C

A

E

D

B F

C A

D

S

CE E F B D A

(34)

B F B

F C CE E A

D

D A

Gli intervalli di “attivazione” di una qualunque coppia di vertici sono:

•

disgiunti, oppure

•

uno interamente contenuto nell’altro

Osservazione

(35)

D B F

C E

12 11 10

9

6 8

1 2 3 4

5 7

A

un vertice non viene “disattivato”

finchè non sono stati “attivati”e

“disattivati” tutti i suoi discendenti

è l’ordine in cui si percorre l’albero delle chiamate ricorsive di una

procedura ricorsiva

progettiamo una versione ricorsiva

dell’algoritmo di visita in profondità

(36)

DFS-VISITA-ricorsiva (G, u) color [u] ← gray

then π[v] ← u

DFS-VISITA-ricorsiva (G, v) color [u] ← black

Una versione (la quarta) ricorsiva dell’algoritmo di visita in profondità

{visita u}

(37)

C'è corrispondenza fra lo stack della procedura

iterativa e lo stack delle attivazioni della procedura ricorsiva.

Più precisamente, supponendo che gli adiacenti vengano visitati nello stesso ordine dalle due

procedure, se ad un certo punto dell'esecuzione lo stack della procedura iterativa è <v

₁

, v

₂

, ..., v

_r

> (con v

₁

= s e v

_r

sul top), la corrispondente sequenza di

attivazioni per la procedura ricorsiva sarà:

<DFS-visit (G,v

₁

), ..., DFS-visit (G,v

_r

)>.

La corrispondenza può essere dimostrata per

induzione sul numero di elementi nello stack.

(38)

Esercizio

• Dimostrare la corrispondenza fra lo stack della procedura iterativa e lo stack delle attivazioni della procedura

ricorsiva.

(39)

DFS-VISITA-ricorsiva (G, u) color [u] ← gray

{visita u}

then π[v] ← u

DFS-VISITA-ricorsiva (G, v) color [u] ← black

Introduciamo un contatore “time” per ricordare l’ordine

delle attivazioni e disattivazioni e i due attributi d (attivazione) e f (disattivazione)

f[u] ← time ← time + 1 d[u] ← time ← time + 1

Modifichiamo l’algoritmo per “sintetizzare” altre informazioni

(40)

INIZIALIZZA (G) for ogni u ∈ V do

color [u] ← white π[u] ← nil

d[u] ← f[u] ← ∞ time ← 0

N.b. Se un vertice non viene “visitato” i suoi tempi di attivazione e disattivazione restano “infiniti”.

Ovviamente gli attributi d ed f e il contatore time

devono essere inizializzati

(41)

DFS-VISITA-TUTTI-I-VERTICI (G) INIZIALIZZA (G)

for ogni u ∈ V do if color [u] = white

then DFS-VISITA (G, u)

Visita in profondità di tutti i vertici di un grafo (orientato o non orientato)

DFS-VISITA-TUTTI-I-VERTICI’ (G) INIZIALIZZA (G)

for ogni u ∈ V do if color [u] = white

then DFS-VISITA-ricorsiva (G, u)

Oppure:

(42)

1. Teorema delle parentesi

In ogni visita DFS di un grafo (orientato o non orientato), per ogni coppia di vertici u, v una e una sola delle seguenti condizioni è

soddisfatta:

• d[u] < d[v] < f[v] < f[u] e u è un antenato di v in un albero della foresta DFS

• d[v] < d[u] < f[u] < f[v] e u è un discendente di v in un albero della foresta DFS

• d[u] < f[u] < d[v] < f[v] e tra u e v non esiste relazione di antenato – discendente nella foresta DFS

Si hanno come corollari

Proprietà della visita in profondità di tutti i vertici (1/5)

(43)

2. Annidamento degli intervalli

Una visita DFS di un grafo (orientato o non orientato), colloca un vertice v come discendente proprio di un vertice u in un albero della foresta DFS d[u] < d[v] < f[v] < f[u]

3. Teorema del cammino bianco

In una foresta DFS un vertice v è discendente di un vertice u al tempo d[u] v è raggiungibile da u con un cammino contenente solo vertici bianchi

(44)

Classificazione degli archi del grafo durante una DFS

Arco di attraversamento: arco che collega due vertici che non sono in relazione antenato - discendente

DEFINIZIONE

Arco dell’albero: arco inserito nella foresta DFS

Arco all’indietro: arco che collega un vertice ad un suo antenato in un albero della foresta DFS

Arco in avanti: arco che collega un vertice ad un suo discendente in un albero della foresta DFS

(45)

OSSERVAZIONE

un arco (u, v) viene “percorso” quando si scopre v nella lista degli adiacenti ad u.

In quel momento color[v] può essere:

• grigio: u è un discendente di v in un albero della foresta DFS, (u, v) è un arco all’indietro

• nero: la visita di v è già terminata, (u, v) è un arco

• in avanti se v è un discendente di u in tal caso d[u] < d[v] < f[v] < f[u]

d[u] < d[v]

• di attraversamento altrimenti

in tal caso d[v] < f[v] < d[u] < f[u]

d[v] < d[u]

Abbiamo un criterio per la classificazione !

• bianco: (u, v) è un arco dell’albero

(46)

Teorema

In una visita DFS di un grafo non orientato , ogni arco è un arco dell’albero o un arco all’indietro.

Teorema

Un grafo, orientato o non orientato , è aciclico se e solo se una visita DFS (qualunque) non produce archi all’indietro.

(47)

Esercizio

• La correttezza della seconda (e della terza) versione dell’algoritmo di visita in profondità segue dalla

correttezza della prima versione dell’algoritmo (che, a sua volta, è conseguenza immediata della correttezza

dell’algoritmo di visita generica, che stata dimostrata con il metodo delle asserzioni). ANNOTATE (SCRIVENDO SULLA STAMPA DEI LUCIDI) IL CODICE DELLA PRIMA, DELLA SECONDA, E DELLA TERZA

Grafi: visita in profondita’