Algoritmi e ricerca operativa - Appunti

DEQUEUE(Q)

esaminati, u diventa nero e viene rimosso dalla coda dei grigi.

color[u]:= BLACK

Effetto dell’algoritmo su un grafo non orientato: 8

L’albero BFS costruito durante l’esecuzione dell’algoritmo è questo:

distanza 0 da s

distanza 1 da s

distanza 2 da s

distanza 3 da s

Complessità dell’algoritmo

Dopo l’inizializzazione, questo test “if color[v]=WHITE” assicura che ogni vertice venga

inserito in Q al massimo una volta e, di conseguenza, che venga eliminato dalla coda al

massimo una volta.

Le operazioni inserimento ed eliminazione da Q richiedono tempo costante O(1), che su un

grafo da V vertici sono O(V) di tempo dedicato su Q. La lista di adiacenza di ogni vertice viene

scandita soltanto quando questo vertice viene tolto da Q, quindi al massimo scandisco la lista

di adiacenza di ogni vertice una volta. 9

Poiché la somma delle lunghezze di tutte le liste di adiacenza (la lunghezza dipende dal

numero di archi E) è Θ(E), il tempo massimo impiegato per scandire tutte le liste di adiacenza

è O(1-E) = O(E).

Il tempo dedicato alla fase di inizializzazione è O(V), quindi il tempo totale della BFS è O(V+E),

che è un tempo lineare.

Applicazioni BFS

1) Calcolare il numero di vertici a distanza k da un vertice v dato.

2) Calcolare il numero di vertici raggiungibili da s.

Def. e teorema importanti per le varianti sul BFS

Def. di albero: Un albero è un grafo non orientato, connesso e aciclico.

Teorema: Se G è un grafo non orientato, allora

G è un albero ≡ G è connesso e |E|=|V|-1 ≡ G è aciclico e |E|=|V|-1

Cioè le tre affermazioni sono equivalenti.

Osservazioni ∞

Se alla fine dell’esecuzione del BFS rimangono nodi bianchi (cioè con d[u]= ) vuol dire che

quei nodi NON sono raggiungibili da s e non appariranno nell’albero BFS costruito durante la

visita (perché di fatto non sono mai stati scoperti). Lo stesso vale per gli archi non calcati.

Esempio:

Grafo di partenza:

Grafo dopo l’esecuzione della BFS:

Albero BFS: ∈

L’informazione contenuta in d[u] per ogni vertice u V mi dice se il

∄

grafo è connesso: se per ogni coppia di vertici un cammino che li

unisce, allora G non è connesso.

Questo implica che non potrò mai visitare quei vertici (rimarranno sempre bianchi e

∞

con distanza da s = . 10

Algoritmo DFS (depth-f rst search, visita in profondità)

Dato un grafo G=(V,E) e uno specifico vertice s chiamato sorgente, la visita in profondità

esplora il grafo andando il più possibile in profondità (allontanandosi sempre più da s).

Nella visita in profondità, gli archi vengono ispezionati a partire dall’ultimo vertice scoperto v

che ha ancora archi non ispezionati che escono da esso. Quando tutti gli archi di v sono stati

ispezionati, la visita fa marcia indietro per ispezionare gli archi che escono dal vertice dal

quale v era stato scoperto. Questo processo continua finchè non saranno stati scoperti tutti i

vertici che sono raggiungibili dal vertice sorgente originale. Se restano dei vertici non

scoperti, allora uno di essi viene selezionato come nuovo vertice sorgente e la visita riparte da

questa sorgente. L’intero processo viene ripetuto finchè non saranno scoperti tutti i vertici del

grafo.

Strutture dati utilizzate:

- Adj[u] = per conoscere i vertici adiacenti di u

- color[u] = può assumere il colore bianco, grigio o nero

- π[u] = predecessore di u

- d[u] = momento in cui viene scoperto u compresi tra 1 e 2|V|

- f[u] = momento in cui si completa la visita di u d[u] < f[u]

u è WHITE prima del tempo d[u]

o u è GRAY fra il tempo d[u] e il tempo f[u]

o u è BLACK dopo il tempo f[u]

o

A differenza della BFS in cui il sottografo dei predecessori formava un albero, ora il sottografo

dei predecessori della DFS può essere composto da diversi alberi perché la visita può essere

ripetuta da più sorgenti diverse. Questo insieme di alberi è una foresta.

DFS(G) ∈ <- inizializzazione di ogni vertice

FOR ogni vertice u V[G]

DO color[u]:=WHITE

π[u]:=NIL

END FOR

time:=0 ∈ <- visita in profondità di ogni vertice non ancora scoperto

FOR ogni vertice u V[G]

DO IF color[u]=WHITE <- ogni volta che DFS_VISIT viene invocata, il vertice u

THEN DFS_VISIT(u)

diventa la radice di un nuovo albero della foresta DFS

END FOR

DFS_VISIT(u)

color[u]:=GRAY

time:=time+1

d[u]:=time ∈

FOR ogni v Adj[u]

DO IF color[v]=WHITE

THEN π[v]:= u

DFS_VISIT(v)

<- uscita del for: ogni arco uscente da u è stato esplorato

END FOR

color[u]:=BLACK

time:=time+1 11

f[u]:=time

Effetto dell’algoritmo su un grafo orientato:

Dopo che

gli archi sono stati

ispezionati

dall’algoritmo, vengono

rappresentati su

sfondo grigio (se sono archi dell’albero) o tratteggiati (non fanno parte di un “percorso

in profondità”, quindi non fanno parte dell’albero). Una volta individuato un arco tratteggiato,

l’algoritmo farà backtracking sulle chiamate ricorsive impostando BLACK tutti i vertici che ha

esplorato.

Componenti connesse ottenute:

Complessità dell’algoritmo

I cicli for della DFS vengono svolti V volte, quindi la procedura DFS ha complessità Θ(V).

La procedura DFS_VISIT è chiamata esattamente una volta per ogni vertice v, perché

DFS_VISIT viene invocata soltanto se un vertice è bianco e la prima cosa che fa è colorare di

grigio il vertice. Durante l’esecuzione della procedura, il ciclo for viene eseguito un numero di

volte che dipende dalla lunghezza delle liste di adiacenza di ogni vertice, quindi il for viene 12

eseguito |Adj[v]| volte. Quindi per sapere il costo totale della procedura devo sommare tutte

∑ ∣ ∣

[ ]

Adj v

le cardinalità delle Adj: = Θ(E).

∈V

v

Il tempo totale di DFS è dunque Θ(V+E).

Applicazioni DFS

1) Ordinamento topologico

2) Conteggio delle componenti connesse

Osservazioni

Il numero di chiamate DFS_VISIT della DFS coincide con il numero di componenti connesse che

produrrà la visita in profondità.

La DFS può essere usata per classificare gli archi del grafo in input. Questa classificazione è

utile per estrarre importanti informazioni sui grafi. Definiamo 4 tipi di archi in termini della

foresta prodotta dalla DFS su un grafo orientato.

- Archi dell’albero: sono gli archi della foresta DFS. L’arco (u,v) è un arco dell’albero se

v è stato scoperto la prima volta esplorando l’arco (u,v).

- Archi all’indietro: sono quegli archi (u,v) che connettono un vertice u ad un antenato

v in un albero DFS. I cappi vengono considerati come archi all’indietro.

- Archi in avanti: sono gli archi (u,v) che non sono archi dell’albero e che connettono un

vertice u ad un discendente v in un albero.

- Archi di attraversamento: sono tutti gli altri. Essi possono connettere vertici nello

stesso albero DFS, purché un vertice non sia antenato dell’altro. Oppure possono

connettere vertici di alberi DFS distinti.

Gli archi tratteggiati non sono archi dell’albero, ma si distinguono

in:

● archi all’indietro

● archi in avanti

● archi di attraversamento

L’algoritmo DFS può essere modificato in modo da classificare gli archi che incontra. L’idea

chiave è che ogni arco (u,v) può essere classificato in base al colore del vertice v che viene

raggiunto quando l’arco viene ispezionato per la prima volta (tranne gli archi in avanti e di

attraversamento che non sono distinti):

- WHITE: arco dell’albero

- GRAY: arco all’indietro

- BLACK: arco in avanti (se d[u]<d[v]) o di attraversamento (se d[u]>d[v])

In un grafo non orientato potrebbe esserci qualche problema di ambiguità nella classificazione

degli archi, perché (u,v) e (v,u) in effetti sono lo stesso arco. In tale caso, se allo stesso arco

possono essere attribuiti più tipi diversi, la priorità verrà data al tipo che compare per primo

nella classificazione per colori fatta sopra. 13

Teorema: In una visita in profondità di un grafo non orientato G, gli archi di G possono essere

archi dell’albero o archi all’indietro. (Non compaiono mai archi in avanti o archi di

attraversamento).

Ordinamento topologico

Posso usare la visita in profondità per effettuare l’ordinamento topologico di grafi orientati

aciclici, chiamati DAG (directed acyclic graph). Un ordinamento topologico di un DAG G=(V,E)

è un ordinamento lineare di tutti i suoi vertici tale che se G contiene un arco (u,v) allora u

appare prima di v nell’ordinamento (se G non è aciclico, allora non è possibile effettuare alcun

ordinamento lineare).

Un ordinamento topologico di un grafo può essere visto come un ordinamento dei suoi vertici

lungo una linea orizzontale in modo che tutti gli archi orientati siano diretti da sinistra a

destra.

Esempio: ordinamento topologico degli indumenti quando un uomo si veste

Ogni arco orientato (u,v) indica che

l’indumento u deve essere indossato

prima dell’indumento v.

Grafo rappresentato secondo l’ordinamento topologico:

I vertici sono ordinati da sinistra a destra in senso decrescente rispetto ai tempi di

completamento f[u]. Inoltre, tutti gli archi orientati sono diretti da sinistra verso destra.

Algoritmo per l’ordinamento topologico:

TOPOLOGICAL_SORT(G)

1) Chiama DFS(G) per calcolare i tempi di completamento f[v] per ciascun vertice v

2) Una volta completata l’ispezione di un vertice, inserisce il vertice in testa alla lista

concatenata

3) return la lista concatenata dei vertici

L’ordinamento topologico ha complessità Θ(V+E), perché la visita in profondità impiega un

tempo Θ(V+E) e occorre un tempo O(1) per inserire ciascuno dei |V| vertici in testa alla lista

concatenata. 14

Dimostriamo la correttezza di questo algoritmo utilizzando il seguente teorema.

Teorema: Un grafo orientato G è aciclico se e soltanto se una visita in profondità di G non

genera archi all’indietro.

Componenti fortemente connesse

La scomposizione di un grafo orientato nelle sue componenti fortemente connesse è

un’applicazione della DFS. Il problema originale viene diviso in sottoproblemi, uno per ogni

componente fortemente connessa, poi le soluzioni possono essere combinate seguendo la

struttura delle connessioni fra le componenti.

Una componente fortemente connessa di un grafo orientato G=(V,E) è un