Appunti Algoritmi e strutture dati

NB: trovare un Source è costoso, trovare un Sink è più semplice

NB: in un grafico aciclico, se rimuovo le source, si creeranno automaticamente nuove source:

DFS può darci tutte le informazioni necessarie: Stampiamo i vertici in ordine post-decrescente

5 , 3 , 1 , 4 , 2 √

+ Dimostrazione correttezza algoritmo (in lavagna)

Individuiamo le componenti fortemente connesse: massimale

Un insieme di vertici, è una componente fortemente connessa, se è rispetto a questa proprietà:

ogni altro vertice"

"da ogni vertice, si può raggiungere

Nei grafi aciclici, le componenti fortemente connesse sono i singoli vertici.

Diamo un nume alla componente connessa

come il vertice di numero minimo che contiene

Vorremmo costruire un output così:

aciclico

NB: il grafo delle componenti connesse è sempre

Hint 1: 2 esecuzioni della DFS può restituirci le componenti fortemente connesse

Hint 2: se il primo restart dell'explore, lo eseguo su un nodo sink ( 3 o 6 o 5 ), rimango sicuramente al suo interno.

ES: partiamo dalla 3 con CC=1 --> i vertici 3 e 6 "si beccano 1"

2* restart: sulla 6 con CC=2 --> vertice 6 "si becca 2"

3* restart: sulla 5 con CC=3 --> vertice 5 "si becca 3"

esaurite le sink, eliminiamo le precedenti (3,5,6) e naturalmente emergeranno nuove sink da cui continuare

4* restart: sulla 4 con CC=4 --> vertice 4 "si becca 4"

...

...

... e sto costruendo l'array

individuare una sink

Quindi il problema sarà da cui cominciare...

Possiamo trovare un vertice che sta in una sink component?

Purtroppo no.

-->

però, è più semplice: source

Trovare un vertice in una component

sink

(diventa un vertice in una component nel grafo trasposto) source

1) Si esegue una DFS(1) --> il vertice con il POST più alto, sta in una component

(per natura della ricorsione)

grafo trasposto post più alto in ordine decrescente

2) DFS(2) sul partendo dal

--> rimango all'interno di quella CFC * immagine di esempio con numeri pre/post

riferiti alle CFC anziché ai vertici in esse contenute

CFC(G)

DFS1(G)

DFS2(G )

DFS 1(G) DFS 2(G )

for each v V do for each v V do

∈ ∈

visited[v] <- false visited[v] <- false

pre[v] = post[v] = 0 ncc=0 post

for each v V do for each v in decreasing order

∈

if not_visited[v] then if not_visited[v] then

explore(G,v) ncc <- ncc +1

explore(G,v)

Recap sugli usi della DFS nei grafi:

1) non orientati --> Calcolo delle componenti connesse

2) orientati aciclici --> Ordinamento topologico

3) orientati --> Calcolo componenti fortemente connesse

Costo computazionale DFS?

for each v V do Ớ(n) viene eseguito per ogni vertice di V

∈

if not_visited[v] then Ớ(n)

explore(G,v) O(n) al massimo n volte: molti vertici possono essere già visitati dopo qualche run

explore(G,v)

visited[v] <- true O(1)

for each u adj[v] do O(n)

∈

if not_visited[u] then O(n)

explore(G,u) O(n)

Ragionamento corretto (ma non preciso):

"ogni volta che chiami la explore, esegui un ciclo per ogni vertice adiacente al vertice su cui hai chiamato la explore"

nel caso "peggiore" ogni vertice è collegato a tutti gli altri vertici:

n n

--> circa chiamate della explore, per ognuna di queste un ciclo su al più elementi --> complessità quadratica O(n )

Analisi più accurata: una volta sola

la explore viene chiamata su tutti i vertici, di ogni vertice viene esaminata la lista di adiacenze,

quindi vengono esaminate TUTTE le liste di adiacenze, una volta sola.

la somma delle liste di adiacenze di tutti i vertici è

Breadth First Search

(ricerca in ampiezza)

NB: DFS non è adatto a cercare le distanze

BFS invece...

1) Esamina la lista di adiacenza del punto di partenza S (es: S=1)

2) Visita i vertici ad esso collegati assegnandogli distanza pari a S+1

in ordine di scoperta

3) Ricomincia da 1) sui suddetti,

Evidenziamo gli archi che sono stati utilizzati per la scoperta

e costruiamo con essi un albero di visita / albero delle distanze:

L'obiettivo è, dato un vertice, trovare le distanze (e i cammini) di tutti gli altri vertici (da quel vertice)

FIFO

Serve una struttura dati d'appoggio adeguata: Coda

Breadth_first_search(G,s) /* G=(V,E) s=vertice da cui calcolare le distanze

for each v V do /* inizializza le distanze di tutti a ∞, ed s=0

∈

dist[v] = ∞

dist[s]=0

Q <- newQueue()

enqueue(Q,s) /* inserisce il vertice di partenza in coda

while not_empty(Q) do /* finchè la coda non è vuota

u <- dequeue(Q) /* estrae il primo elem. dalla coda

for each v adj[u] do /* ne esamina la lista di adiacenza

∈

if dist[v] = ∞ then /* se trova vertici inesplorati(∞)

dist[v] <- dist[u]+1 /* imposta loro la distanza dell'elem. corrente +1

enqueue(Q,v) /* e inserisce questi ultimi in coda da esaminare

NB: Questa soluzione provvede solo le distanze (in array) ma non il cammino!

analizziamo un attimo l'albero delle distanze:

da 1 a 4

Non è facile calcolare il percorso

tutti

senza passare per i vertici... rovesciato

sarebbe più semplice se l'albero fosse

girati)

(e quindi gli archi da 4 a 1

per poterlo ripercorrere al contrario ..!

Come vedremo, non è difficile costruire

una struttura dati atta a memorizzare i cammini

Calcolo del cammino minimo su grafi pesati

Potremmo riciclare l'idea della BFS per il calcolo del cammino minimo, sostituendo il valore del peso con un numero di archi fittizi -1 :

Il problema principale è il costo computazionale al crescere del peso degli archi!

Altro esempio:

Osservazione:

L'algoritmo non fa niente, finche "l'onda" non arriva ad un vertice significativo (non dummy)

non è davvero necessario eseguire i passi intermedi! potremmo "svegliare" l'algoritmo solo quando l'onda arriverebbe ai vertici adiacenti

Distanza Peso arco Provenienza

Alcuni vertici sono raggiunti da più archi

In questi casi, deve essere mantenuto il tempo

e il cammino la cui somma degli archi è inferiore.

ES: 1,3,2 tempo 2

vince su 1,2 tempo 4

Eventi (in sequenza): 3

e1 --> 1 onda arriva al vertice ( da 1)

2

e2 --> 4 onda arriva al vertice 2

e3 --> 2 onda arriva al vertice ( da 3)

5

e4 --> 3 onda arriva al vertice ( da 3)

4

e5 --> 6 onda arriva al vertice 5

e6 --> 3 onda arriva al vertice ( da 2)

4

e7 --> 5 onda arriva al vertice ( da 5)

6

e8 --> 5 onda arriva al vertice ( da 5)

6

e9 --> 6 onda arriva al vertice ( da 4) interrogabile.

Come/Dove salvare i risultati? La struttura dati risultante è

1 6

ES: da voglio andare a

Semplice, perché ogni vertice ha un solo padre, mentre tutti i vertici possono avere più figli.

Problema:

Nel caso in esempio, l'ordine di scoperta (dettato dall'indice) è:

e1 l'onda arriva a 3

e2 l'onda arriva a 2

e3 l'onda arriva a 4 (t6)

e4 l'onda arriva a 4 (t4)

e3 viene eseguito prima,

ma il tempo d'arrivo è successivo.

Se ci limitassimo a non conservare il percorso dell' e4 perché già scoperto all'evento e3, otterremmo un percorso più lungo.

Soluzione:

Ogni volta che viene scoperto un tempo migliore, si aggiorna tempo e percorso. --> Operazione decrease_key(key,priorità)

Operazioni fondamentali definite sulla coda con priorità:

* Costruttore

* Estrazione del minimo

* Inserimento

* Decremento chiave (decrease_key)

Scriviamo l'algoritmo in pseudo codice...

Algoritmo di Dijkstra - Shortest_Path

Shortest_path(G,s)

for each v V do

∈

D[v] <- ∞

P[v] <- nil

d[s] = 0

Q <- new_priority_queue()

(usando D come priorità)

insert(Q,s)

while not empty(Q) do

u <- extract_min(Q)

for each v adj[u] do

∈

if D[v] > D[u] + w then

(u,v)

D[v] <- D[u] + w (u,v)

P[v] <- u

decrease_key(v,D[v])

Come realizzare una struttura dati con queste caratteristiche?

tutte

1) Se le chiavi vengono inserite una sola volta, può bastare questo: 2) Altrimenti:

• make() (costruttore) --> O(1) //allocazione di memoria

n

• insert(Q,k,p) --> O(1) // grazie ad che punta al primo elem. libero

• extract_min(Q) --> Θ(n) // il min va cercato, e l'eventuale "buco" in mezzo alla sequenza và "chiuso" compattando l'array

• decrease_key(Q,k,p) --> O(n) // ma anche O(1) avendo l'indice

Possiamo fare di meglio?

Heap dall'alto verso il basso, sinistra verso destra)

è una struttura dati ad albero binario, completo. (ovvero tutti gli elementi sono inseriti da

rappresentabile anche tramite array

min heap: struttura

1) Proprietà di (albero binario completo) non decrescenti)

heap

2) Proprietà di (per ogni cammino radice-foglia, i valori sono

Rappresentazione su array:

Per la particolare natura di questa struttura (ogni padre ha *tipicamente* 2 figli)

è possibile stabilire la relazione padre-figlio mediante la semplice regola:

2i 2i+1 2i ≤ n 2i +1 ≤ n

Dato l'elemento i-esimo, i figli sono (sinistro) e (destro) - se esistono ovvero, se e/o

Notiamo che l'array risultante non è ordinato.

sicuramente Heap!

Però... un array ordinato è uno

Insert:

• vogliamo inserire la chiave 11 con priorità 5

O( Log(n) )

altezza dell'albero:

Costo computazionale:

Extract_min:

• sempre

Per la natura del min heap, il minimo sta nella radice.

Problema: "tolgo"

se il minimo (cioè la radice), ottengo 2 alberi separati, e non è ciò che vogliamo.

Soluzione: L'unica chiave che posso inserire al suo posto, senza creare buchi, è l'ultima inserita.

faccio salire

il più piccolo

tra i due figli

O( Log(n) )

Costo:

NB:

questa soluzione (Heap) è molto migliore della precedente:

è vero che la insert costa O(logn) anziché O(1), ma extract_min costa O(logn) anziché Θ(n)!!!

Decrease_key:

• vogliamo portare la priorità della chiave 11 da 5 a 2

Ogni volta che modifichiamo il valore di una chiave, la proprietà di heap sarà quasi sicuramente persa. (necessario fix up)

Problema:

Abbiamo perso l'accesso diretto. il numero di chiave non corrisponde più alla posizione dell'array.

ES: chiave 6 pos. 6 OK

chiave 5 pos. 7 PROBLEMA

...

Soluzione:

Serve una struttura dati c