N o 1. BFS - trovare il numero di cammini minimi da u agli altri nodi

(1)

N 1. BFS - trovare il numero di cammini minimi da u agli altri nodi

Notazione

・

Adj[v] : lista di adiacenza del nodo v

- il grafo è rappresentato mediante liste di adiacenza

・

Enqueue(S, x): aggiunge x alla coda S

・

Dequeue(S): ritorna l’elemento in testa alla coda S e lo rimuove da S

・

Dist[v]: la distanza di v da u

・

Paths[v]: il numero dei cammini da u a v di lunghezza Dist[v] (lunghezza minima)

・

visited[v]: uguale a true se il vertice è già stato visitato

1

BFS(G, u)

Set visited[v] = false, Paths[v] = 0, Dist[v]= ∞ for each v Enqueue(S, u), visited[u] = true, Paths[u] = 1, Dist[u] = 0 while (S is not empty) {

w ⟵ Dequeue(S) // visited[u] rimane true

for each z in Adj[w]

if (visited[z] = false)

Dist[z] = Dist[w]+1, Paths[z] = Path[w]

visited[z] = true Enqueue(S,z)

else if (Dist[z] = Dist[w]+1) Paths[z] = Paths[z] + Paths[w]

(2)

N 2. Problema del Cambia-monete e Algoritmo del cassiere

Tagli di moneta: 1c, 5c, 10c, 20c, 25c

・

l’algoritmo del cassiere fallisce

- x = 43 Algo Cassiere -> 25+10+5+1+1+1 Altra soluzione (migliore) -> 20+20+1+1+1

Modifichiamo l’insieme dei tagli

Eliminazione di un taglio. Se eliminiamo la moneta da 25c, possiamo ripetere la prova vista a lezione e dimostare che l’algoritmo del cassiere funziona.

Aggiunta di un taglio. Se aggiungiamo la moneta da 15c, recuperiamo l’ottimalità dell’algoritmo del cassiere.

Esiste una soluzione ottima che contiene al più:

(3)

N 3. Complessità dell’Algoritmo del cassiere

Versione vista a lezione:

・

^cⁿè il taglio massimo

・

^{al più x/c}ⁿ volte viene ripetuto il ciclo per inserire una moneta da cn

・

le restanti volte viene inserita al più 1 moneta degli altri tagli - quindi al massimo altre n-1 iterazioni

・

totale O(x/cn + n)

・

questo potrebbe essere O(2^{log x}/cn + n) quindi esponenziale in log x

Versione migliorata:

・

se, quando l’algoritmo vuole aggiungere alla soluzione monete di taglio cn, al posto di iterare, calcola direttamente quante volte cn entra in x, eseguendo la divisione x/cn a costo O(1)

- la complessità diventa O(n)

3

(4)

N 4. Ricerca dei nodi critici meno efficiente - Complexity O(n m)

for each v in V

nodi_in_visita_G-v ⟵ BFS-conta (G, v) if (nodi_in_visita_G-v < n-1) then

Output “v è nodo critico”

endif endfor

BFS-conta(G, v) // Questa procedura esegue una visita BFS su G-v e conta i nodi visitati

u ⟵ first node in Adj[v] // scegliamo un nodo in G-v da cui cominciare Set visited[z] = false for each z in V-v

Enqueue(S, u), visited[u] = true, conta ⟵ 1 while (S is not empty) {

w ⟵ Dequeue(S) // visited[u] rimane true for each z in Adj[w]

if (z ≠ v) and (visited[z] = false) // escludiamo v perché siamo in G-v

Eseguiamo per ogni nodo v una BFS nel grafo G-v

se visitiamo meno di n-1 vertici (tutti quelli di G-v allora vuol dire che G-v non è connesso

quindi v è critico

Ogni BFS costa O(m+n), ne facciamo n, quindi la complessità totale diventa O(nm)

(5)

N 4. Nodi critici mediante visita DFS - Complessità O(n+m)

5

Set t = 0,

Set min_t[v] = ∞, numchild[v] = 0, visited[v] = false for each v Execute DFS-critici(r)

if numchild[r] > 1 then Output “r è critico”

for each v ≠ r

if (min_t[v] >= time[parent[v]]) then Output “parent[v] è nodo critico”

DFS-critici(v) // versione adattata di DFS t = t + 1

visited[v] = true, time[v] = t, min_t[v] = t for each u in Adj[v]

if (visited[u] = false)

add edge (v,u) to the BFS tree T, parent[u] = v, numchild[v] = numchild[v]+1

DFS(u)

min_t[v] = min{min_t[v], min_t[u]}

endif

if (u ≠ parent[v])

min_t[v] = min{min_t[v], time[u]}

La radice dell’albero DFS è nodo critico se e solo se ha più di un figlio

Una foglia dell’albero DFS non è mai nodo critico

Un nodo interno v (non radice) dell’albero DFS è nodo critico se e solo se ha almeno un figlio w tale che tutti i discendenti di w non hanno archi verso vertici visitati prima di v

(6)

Proprietà della visita DFS per la scoperta dei nodi critici

Osservazione.

・

se (u,v) è un arco del grafo G ed (u,v) non è un arco dell’albero DFS, allora, nell’albero DFS o u è antenato di v o viceversa.

・

chiamiamo un tale arco (che esiste solo nel grafo) un collegamento all’indietro

・

un nodo v (non radice dell’albero DFS) è un nodo critico se e solo se nessuno dei nodi incontrati durante la DFS partita da uno dei suoi figli ha un collegamento all’indietro verso un antenato di v

v

w z

In questa parte ci sono i nodi visitati

prima di v

u collegamento

all’indietro tra x e z

Se nessuno dei nodi visitati da w ha un collegamento all’indietro