Che materia stai cercando?

Anteprima

ESTRATTO DOCUMENTO

• Lefthost_child(n,T) -> ritorna il nodo più a sinistra tra i figli del nodo n nell'albero T

• Right_sibling(n,T) -> ritorna il fratello di destra del nodo n nell'albero T

• Label(n,T) -> ritorna l'etichetta del nodo n nell'albero T

• Create(v,T1,…,Tn) -> crea un albero che ha come radice il nodo v e ha come figli le radici degli alberi

T1,T2…)

• Root(T) -> ritorna la root dell'albero T

• Makenull(T) -> rende l'albero T nullo

Albero implementato con Array

Un albero implementato tramite array è un array T[1, … , n] dove n è il numero di nodi e T[i] = j indica che il

nodo j-esimo è il genitore del nodo i-esimo in T. in altre parole:

I nodi sono rappresentati dalla celle di un array, che per ciascuno di essi contengono l'indice della cella del

proprio genitore.

Pro e contro

Pro:

• è efficiente trovare il genitore

Contro:

• Costoso trovare i figli di un nodo

• Si perde l'ordine dei figli di ciascun nodo, se non si adotta una convenzione per cui i figli di ciascun

nodo seguono un dato ordine dell'array T

Albero implementato con liste di figli

Ogni nodo ha associata la lista dei suoi figli.

Qualsiasi implementazione di lista va bene per rappresentare i figli.

Algoritmi e strutture dati Pagina 13

ALGO 5° Lezione

martedì 20 ottobre 2015 13:39

Algoritmi di visita

Vi sono vari tipi di metodi per "visitare" un albero, distinguiamoli in varie classi:

• In Profondità: partendo dalla radice, si cerca di scendere sempre più in profondità.

○ Pre-ordine (GDBACFEIHJ)

○ In-ordine (ABCDEFGHIJ)

○ Post-ordine (ACBEFDHJIG)

• In Ampiezza

Visita l'albero livello per livello, partendo dal nodo radice

Preordine

L'algoritmo di visita in preorder si sviluppa in questo modo.

1. Viene visitato n

2. Visito in preordine i figli di n da sinistra verso destra (T1,T2, ecc)

Implementazione

Label(n)

C = n.children (lista dei figli?)

While c!=NULL

Pre_order(c)

c=c.next

In-order

1. Visita, in-order, il primo figlio a sinistra di n (il più a sinistra)

2. Visito il nodo n (root del sottoalbero)

3. Visito in-order, il 2°,3° fino al k° figlio di n da sinistra verso destra

Implementazione

IN_ORDER(n)

c=n.children

If c != NULL //se la lista dei figli non è vuota

procede con la funzione

In_order(c)

Label(n) //visita la radice

Algoritmi e strutture dati Pagina 14

Label(n) //visita la radice

c=c.next // vado avanti al prossimo figlio

While c!= NULL //termina ricorsione

In_order(c )

c=c.next

Post Order

1. Visito prima il sottoalbero sinistro di n

2. Visito il sottoalbero destro di n

3. Visito il nodo n

Implementazione

c=n.children

While c!=NULL

Post_order( c )

c=c.next //vado avanti al prossimo figlio

Label(n) //visito la radice

Algoritmi in ampiezza

Un albero viene "scomposto" da vari "livelli", ossia ogni "salto" di "generazione"

Un algoritmo in ampiezza parte dalla root , e analizza l'albero livello per livello.

Nel caso nel disegno iniziale dell'albero, l'ordine dei nodi visitati sarà GDI,BFHJ,ACE.

Implementazione: Breadth.first.search(t)

Costruiamo una coda, di nome q:

q=new.queue()

Enqueue(T,q) //inserisce la coda nel nostro albero

While NotEmpty(q) //finchè la coda non è vuota

n=dequeue(q) //estraggo il nodo dalla coda

Label(n)

c=n.children

While c!= NULL

Enqeue(c,q) //inserisco i figli del nodo appena visitato

c=c.next

Alberi binari di ricerca

Un albero binario è un albero in cui ogni nodo presenta solo due figli: uno a sinistra e uno a destra.

Ogni nodo può avere:

1. 0 figli

2. 1 figlio sinistro n.left

3. 1 figlio destro n.right

4. Un figlio sia a sinistra che a destra

Ogni nodo è composto in questo modo: presenta un elemento key, ossia il contenuto stesso del

nodo, un puntatore parent che punta al proprio padre, un puntatore left e uno right che puntano

rispettivamente ai due figli. Algoritmi e strutture dati Pagina 15

rispettivamente ai due figli.

In un albero binario gli elementi sono ordinati

• Un albero binario di ricerca, se

a. Il valore dei nodi nel sottoalbero sinistro di n è MINORE di n

b. Il valore dei nodi nel sottoalbero destro di n è MAGGIORE di n

Quindi, la visita in order dell'albero produce l'elenco dei valori ordinati

Il vantaggio degli alberi binari di ricerca è che per cercare un elemento x non è necessario visitare

l'albero: basta sfruttare le proprietà e l'ordinamento degli elementi che compongono l'albero.

Tree_Search(n,k)

K è l'elemento da cercare all'interno di un albero.

If n.key==k & n==NULL

Return(n)

If n.key>k

Return (tree_search(n.left,k))

Else Return(tree_search(n.right,k))

Tree_minimum(n)

While n.left != NULL

n=n.left

Return(n)

Tree_maximum(n)

While n.right != NULL

n=n.right

Return(n)

Tree_successor(n)

If n.right != NULL

Tree_minimum(n.right)

y=n.p

//n.p -> genitore

While y != NULL & n ==y.right

n=y

y=y.p

Return y

Inserimento

Visito l'albero cercando v: inserisco v come una nuova foglia.

TREE_INSERT(R,z)

y=NULL Algoritmi e strutture dati Pagina 16

y=NULL

x=T.root

While x!=NULL

y=x

If z.key <z.key

x=x.left

Else x=x.right

z.p=y

If y==NULL

T.root = z

Elseif z.key <y.key

y.left = z

Else y.right = z

Cancellazione

TREE_DELETE(T,z)

if z.left==NULL

Translplant(T,z,z.right)

if z.right=NULL

Translplant(T,z,z.left)

else y=TreeMinimum(z.right)

if y.p!=z

Transplant(T,y,y.right)

y.right=z.right

y.right.p=y

Transplant(T,z,y)

y.left=z.left

y.left.p=y

TRANSPLANT(T,w,v)

if w-p=NULL

R=v

elseif u=u.p.left

u.p.left=v

else u.p.right=v

if v!=NULL

n.p=w.p Algoritmi e strutture dati Pagina 17

ALGO 6° Lezione

martedì 27 ottobre 2015 13:38

Alberi

Si intende come albero completo un albero in cui:

• Tutte le foglie sono alla stessa altezza

• Tutti i nodi intermedi hanno 2 figli

Un albero è bilanciato quando ) (h altezza)

Bilanciamento perfetto

Il bilanciamento perfetto si ha quando il numero di nodi nel sottoalbero sinistro di x differisce al più di 1 del numero di

nodi del sottoalbero destro di x. L'altezza di un albero perfettamente bilanciato deve essere la minima possibile.

Tuttavia bilanciare perfettamente un albero non è sempre facile da eseguire: vediamo ora delle tecniche per bilanciare

gli alberi, non perfettamente.

Alberi bilanciati

• Alberi AVL: l'altezza del sottoalbero destro di x e l'altezza del sottoalbero sinistro di x differiscono al più di 1.

Questo tipo di albero garantisce il bilanciamento tramite rotazioni

• Alberi rossoneri: questi alberi garantiscono che nessun "cammino" che parte dalla radice, è lungo più del doppio

di un altro cammino

• Treap: fornisce una garanzia probabilistica che l'altezza sia O(log2 n) poiché associa un peso casuale ad ogni nodo

e vengono utilizzate rotazioni per garantire il bilanciamento

• Alberi 2-3: tutte le foglie hanno uguale altezza: viene garantito il bilanciamento tramite:

○ Merge + split

○ Grado variabile

• Alberi B e B+: tutte le foglie sono allo stesso livello.

Alberi AVL

Gli alberi AVL sono bilanciati in altezza.

Criterio di bilanciamento:

Ossia, per ogni nodo x l'altezza del suo sotto albero di destra differisce da quella del suo sottoalbero di sinistra al

massimo di 1

Un albero AVL non è MAI alto più del 45% in più rispetto all'albero perfettamente bilanciato che contiene gli STESSI

valori.

L'inserimento o la cancellazione di un nodo può portare allo sbilanciamento di un albero bilanciato: questo perché la

posizione in cui viene inserito un certo elemento è fissata, e non si può decidere a piacere dove inserire un nodo.

Algoritmi e strutture dati Pagina 18

posizione in cui viene inserito un certo elemento è fissata, e non si può decidere a piacere dove inserire un nodo.

Per ovviare a questo problema si utilizzano le rotazioni.

Rotazione

Vi sono due tipi di rotazioni: rotazione singola e rotazione doppia.

In questo caso una rotazione singola è utile per bilanciare i nodi x o z (rispettivamente per l'immagine a sinistra e a

destra). Nel caso dell'immagine di sinistra eseguendo la rotazione il nodo k2 "scende" e diventa un figlio di k1, il quale

diventa root. A suo modo il nodo x "sale" arrivando allo stesso livello di k2.

Facciamo un esempio, bilanciando un albero formato da 7 nodi:

Tuttavia se volessi bilanciare y la rotazione singola non basta, bensì dovrò adoperare la rotazione doppia.

Algoritmi e strutture dati Pagina 19

Una rotazione doppia è semplicemente l'insieme di due rotazioni singole. Grazie a questo tipo di rotazione riusciamo a

bilanciare il nodo y presente nell'immagine precedente.

Ecco un esempio per chiarire bene il tutto:

Inserimento albero AVL del valore x

1. Inserisco x in T seguendo la regola del Binary Search Tree

2. Partendo dalla nuova foglia seguo il path verso la root e controllo se la proprietà di bilanciamento AVL è

soddisfatta

3. Al primo nodo sbilanciato applico la rotazione

a. Se concorde: rotazione singola

b. Se discorde: rotazione doppia

Cancellazione di x da un albero AVL

1. Cancellazione come da normale albero AVL

2. Partendo dal nodo rimosso e salendo verso la root, controllo il bilanciamento AVL

B-Tree

1. Tutte le foglie sono allo stesso livello

2. Hanno un grado molto elevato

Possiamo considerarli come degli alberi "molto piatti e larghi"

Con n=numero di valori e m = grado dell'albero

Diamo una definizione ai B tree:

Un B-tree di grado m soddisfa la seguenti proprietà:

• La radice o è una foglia oppure è un nodo con almeno 2 figli

• Ogni nodo interno ha fra ceiling[ e m figli

• Tutti i path della root a una foglia sono lunghi uguale

(da completare)

Inserimento in albero B Algoritmi e strutture dati Pagina 20

Inserimento in albero B

Se devo inserire il valore k, cerco k nell'albero T e lo inserisco nella foglia raggiunta.

Nel caso la foglia sia piena eseguo l'operazione di SPLIT & PROMOTION, ossia "spezzo" la foglia in 3, e "promuovo" una

delle tre nuove foglie ad un livello superiore. Lo split viene in genere effettuato in mezzo alla foglia.

Lo split si potrebbe prorogare in alto: nel caso peggiore si "spezza la root"

• Anticipare lo split

Nel visitare l'albero alla ricerca di k, spezzo ogni nodo pieno trovato lungo il cammino: in questo modo risparmio tempo.

ESEMPIO

Cancellazione di k da albero B

• Cerco k nell'albero T

• Cancello k

• Garantisco che ogni nodo abbia più di ceiling[m/2] figli

L'inverso dell'operazione di split è l'operazione di merge: (inserisci)

Complessità alberi B

Costo della cancellazione di un elemento in un albero B:

h corrisponde circa a

"piccolo esercizio veloce"

m=7

[m/2] = [7/2] = 4 numero minimo di figli

Creare un albero b con i seguenti elementi:

F,S,Q,K,C,L,H,T,V,W,M,R,N,P,A,B,X,Y,D,Z,E

Tali elementi vanno inseriti nell'ordine in cui sono proposti, e dovranno risultare ordinati (ossia in ordine alfabetico)

Insiemi

Un insieme è una collezione i elementi dove ciascun elemento è un insieme oppure un atomo (elemento di tipo base)

NON ci sono mai elementi uguali

In genere gli elementi sono tutti dello stesso tipo (soprattutto gli atomi)

E vale una relazione d'ordinamento.

Operazioni base Algoritmi e strutture dati Pagina 21

Operazioni base

Union(A,B)

Intersection(A,B)

Difference(A,B)

Merge(A,B)

Member(x,A)

Insert(x,A)

Delete(x,A)

Min(A)

Max(A)

Find(x)

Implementazione di insiemi

Si può implementare un insieme in 2 modi:

1. Bit vector

2. Liste ordinate

Bit Vector

Un insieme può essere implementato tramite bit vector sono se l'insieme U (universo) è di piccole dimensioni e

rappresentabile con l'insieme {0,1,2,3….n}

Costruiamo un array S che rappresenta il nostro insieme Universo:

Metteremo uno 0 in ogni casella in cui il numero non è presente nel nostro insieme ed un 1 in ogni casella incui il

numero è presente all'interno del nostro insieme.

Costo operazioni elementari:

• Insert, delete, member

• Max, min

Union -> OR bit a bit

Intersection -> AND bit a bit

Differenza -> AND + NOT

Implementazione con liste linkate

Elenchiamo vantaggi e svantaggi di questo tipo di implementazione:

• Lo spazio occupato è proporzionale al numero di elementi nell'insieme

• Non è necessario avere un insieme universo di riferimento e se c'è ed è grande non è un problema

Svantaggi:

• Alcune operazioni sono meno efficienti

Possiamo implementare un insieme in due tipi di liste, in una lista ordinata o una lista non ordinata.

Lista non ordinata

In un insieme implementato in una lista non orientata, le seguenti operazioni si effettuano così:

• Unione: Basta accodare le due liste: il next dell'ultimo elemento di A punta a B.head

• Intersezione: per ogni elemento in A bisogna cercare se compare anche in B, scorrendo tutta b, e se lo trova,

inserirlo in C

• Differenza: opera come l'intersezione, solo che inserisce in C gli elementi di A non trovati in B

• Member: Scorre tutta la lista alla ricerca dell'elemento x di interesse (lo stesso vale per delete, insert, max, min)

Lista ordinata

• Unione, intersezione, differenza: Si scorrono le lista di A e B in parallelo, fermandosi appena il valore di una è

uguale o supera quello dell'altra per eseguire l'operazione di interesse sul risultato C

Tabelle di Hash Algoritmi e strutture dati Pagina 22

Tabelle di Hash

Una tabella di hash è un vettore dove alloco i miei valori con un criterio dato dalla funzione di hash.

Ha 2 vantaggi principali:

1. Mantiene una dimensione occupata su k

2. Mediamente il costo di insert, delete, e member è O(1)

Nelle tabelle di Hash non vi è nessuna relazione d'ordine.

Funzione di hash

Nello spazio K avremo un certo valore h(v) il quale risultato della funzione sarà l'indirizzo della cella nella tabella di ha sh

dove trovare il dato.

Quindi, per trovare la posizione di un certo elemento v, ci basta fare h(v), e troveremo l' indice di v all'interno della

tabella T.

La migliore funzione di hash fa in modo che v non centri nulla con w: per ciò serviranno funzioni matematiche complesse

Open Hashing

L'open hashing serve per risolvere le colisioni utilizzando il "chaining": tutti gli elementi che collidono in un valroe di

hash sono inseriti in una lista linkata puntata dall'elemento della tabella di hash che corrisponde al valore di hash su cui

si verifica la collisione

Per implementare le operazioni di memeber, insert, delete basta utilizzare le operazioni omonime definite per le liste

linkate, considerando come head il puntatore T[h(key)] dove key è il valore da cercare

In questo caso, per evitare che due elementi in k vengano inseriti in una stessa casella, nella casella di T verrà inserita u n

insieme di puntatori che puntano ad una lista che conterrà i vari elementi. In questo modo evitiamo la collisione.

Funzioni di hash

Una buona funzione hash distriuisce in modo piuttosto uniforme ciascuna chiave.

• Metodo della divisione: ciascun valore k viene mappato al resto della sua divisione per il numero B di bucket

h(K) = k mod B

Pro: è molto veloce da calcolare

Contro: attenzione a scegliere il valore di B

• Metodo della moltiplicazione = diviso in due fasi: la prima moltiplica k per una costante A compresa tra 0 e 1,

estraendo la parte frazionaria del risultato, e poi modifica il risultato per B e considera l'intero rispetto al risultato

ottenuto

H(k) = [B(kA mod 1)]

Closed hashing (open addressing)

Nel closed hashing non vengono utilizzate strutture esterne per gestire le collisioni, ma tutti i valori sono memorizzati in

una cella nT, che può quindi diventare piena.

Il load factor (non può mai eccedere 1)

Algoritmi e strutture dati Pagina 23

Il load factor (non può mai eccedere 1)

Non vengono utilizzati i puntatori fra le celle di T, bensì un metodo di re-hosting, un metodo per trovare, per ciascuna

chiave tutti i blocchi dove potesse essere memorizzata

• Probe sequence: per una chiave K è la permutazione dei valori <0,1 ..B-1> che corrisponde nell'ordine in cui viene

valutato allo spot in cui k può essere memorizzato nel caso non ci siano collisioni

La funzione hash è definita come

E ritorna, data la chiave k e la posizione desiderata, il corrispondente elmento nella probe sequence

Per inserire un valore k in T, prima valuto h(k, 0): se è pieno provo ad inserirlo in h(k,1) e così via finchè non trovo (se

esiste) una posizione libera.

HASH_INSERT(T,K)

i=0;

Repeat

j= h(k,i)

If T[j] == NULL

T[j] = k

Return j;

Else i = i+1

Until i==B

Return "overflow"

Per cercare un valore proccedo in modo analogo: seguo la sequenza finchè non trovo il valore cercato o un blocco vuoto.

HASH_SEARCH(T,k)

I = 0

Repeat

j=h(k,i)

If T[j] == k return j;

i= i+1;

Until T[j] == NULL OR i == B

Return NULL

Per cancellare un valore non si può semplicemente mettere vuoto il blocco a null poiché verrebbe interrotta la probe

sequence: è necessario un valore speciale "deleted" che non blocchi la ricerca con il primo incontrato, ma al contrario

consenta di inserire un valore al suo posto quando lo incontro nella probe sequence.

• Uniform Hosting: la probe sequence di ogni chiave ha uguale probabilità di ssere una delle B! permutazioni di

<0,1,…,B-1>

• Linear probing: data una funzione di hash h' = U -> {0,1, … , B-1} detta funzione hash ausiliaria il metodo del linear

probing usa la seguente funzione hash:

(in altre parole, se ad esempio 40%7=5 viene inserito nella cella i, il valore successivo 47%7=5 verrà inserito nella

cella i+1 o, se è alla fine dell'array, all'inizio dell'array stesso.)

• Quadratic probing: data la funzione hash ausiliaria h', la funzione di hash è

Algoritmi e strutture dati Pagina 24

• Quadratic probing: data la funzione hash ausiliaria h', la funzione di hash è

Con c1,c2 costanti ausiliarie positive, e c2 != 0

Data una chiave k, prima mappa a T[h'(k)] e poi a posizione che dipendono in modo

quadratico dalla posizione i nella sequenza di probe

• Double Hashing: Il double hashing è uno dei metodi migliori disponibile per l'open hashing. Il double hashing

utilizza due funzioni ausiliarie h1 e h2, e la funzione viene definita in questo modo:

Data una chiave k, prima viene mappata a T[h1(k)] e poi a valori la cui distanza da h1(k) dipende da un'altra

funzione hash, ossia h2(k). Tramite questo metodo si arriva a permutare un numero di probe sequence pari a

Algoritmi e strutture dati Pagina 25

ALGO 7° Lezione

sabato 21 novembre 2015 13:40

Grafi

Un grafo è una coppia (V,E) dove:

• V è un insieme finito di elementi, detti nodi (o vertici o punti)

• E è un insieme di archi (orientati)

Un arco orientato è una coppia ordinata (v1,v2) dove v1 e v2

V1 è la coda dell'arco e v2 è la testa. (l'arco va da v1 a v2) in un arco non orientato non vi è questa

puntualizzazione.

Un grafo con solo archi orientati si chiama grafo orientato.

Un grafo con solo archi non orientati si chiama grafo non orientato. In questo caso, se un arco è

incidente nei vertici v1 e v2, allora questi due vertici sono neighbors.

Due vertici sono adiacenti quando essi sono collegati tra loro da un arco. Nel caso di un arco orientato si

parla di non simmetria mentre nel caso di un arco non orientato si parla di simmetria.

Il grado di un vertice in un grafo non orientato è il numero di archi in cui è coinvolto. (degree)

In un grafo orientato abbiamo l'In-degree, ossia il numero di archi che entrano nel nodo, e l' out-degree,

ossia il numero di archi che escono dal nodo. La somma di essi da il degree.

Identifichiamo un cammino: un cammino da un vertice v1 ad un vertice vi è pari al numero di archi che

si percorrono per arrivare a vi

Un cammino si dice semplici quando tutti i vertici, ad eccezione del primo o dell'ultimo, sono distinti.

Un cammino che inizia e finisce nello stesso vertice si dice ciclo.

Implementazione di un Grafo

Per implementare un grafo, si utilizzano le matrici di adiacenza e le liste di adiacenza:

Matrice di adiacenza

• Assumiamo che i vertici sono numerati, in modo arbitrario. Allora possiamo considerare la matrice

di adiacenza di un grafo come:

Lista d'adiacenza

• Per lista di adiacenza si intende un array, formato da |v| elementi, in cui ciascun elemento è una

lista di vertici, tali che esiste un arco (w,v)

Algoritmi e strutture dati Pagina 26

Vantaggi/Svantaggi

Vantaggi/Svantaggi della matrice di adiacenza:

• + determino in tempo costante se (w,v)

- richiede molto spazio, ossia

Vantaggi/Svantaggi delle liste di adiacenza:

• + lo spazio occupato è di

• È costoso determinare se (w,v)

In linea di massima la matrice di adiacenza è consigliata quando il grafo è molto denso (|E| ondina |V|^

2)

Le liste di adiacenza invece sono ideali quando il grafico è sparso (|E| << |V|^2)

Attraversamento di grafi

Per risolvere molto problemi legati ai grafi si utilizza un metodo di visita del grafo, chiamato

attraversamento.

Analizziamo due approcci di attraversamento:

• BFS (breadth first search - in ampiezza)

• DFS (depth first search - in profondità)

BFS

Dato un grafo G(V,E) ed un nodo sorgente s, la BFS esplora gli archi in C per scoprire ciascun vertice

raggiungibile da S.

Inoltre calcola la distanza di ciascun vertice da S

Questo algoritmo funziona con qualsiasi tipo di grafo, orientato o non.

BFS(G,S)

For each vertex w in G.V - {s}

w.color = WHITE

w.d = infinito

w.p = NULL

s.color = GRAY

s.d = 0

s.p = NULL

Q = NULL

ENQUEUE(Q,S)

While q != NULL

W = DEQUEUE(Q)

For each v in G.adj[w] //nodi adiacenti

If v.color = WHITE

v.color = gray

v.d = w. + 1

v.p = w

ENQUEUE(Q,v)

w.color = black Algoritmi e strutture dati Pagina 27

w.color = black

La BFS garantisce la costruzione di un Breadth First Tree radicato in S e con tutti i nodi raggiunti

dall'algoritmo; inoltre il cammino da s a ciascun vertice nell'albero, è il più corto possibile

L'albero ottenuto dall'esecuzione dell'algoritmo può essere diverso a seconda dell'ordine di vista dei

nodi; tuttavia la distanza non cambia.

IL costo dell'operazione di BFS è O( |V| + |E| )

Algoritmi e strutture dati Pagina 28

ALGO 8° Lezione

domenica 29 novembre 2015 19:17

Depth First Search

Consideriamo un grafo G(V,E) ed un nodo sorgente s la DFS esplora gli archi che escono dal nodo v

raggiunto più di recente che ha ancora archi ordinati non esplorati.

Quando tutti i nodi uscenti da v sono stati esplorati, l'algoritmo torna indietro per esplorare gli archi

uscenti dal nodo che ha permesso di scoprire v.

• L'algoritmo funziona con grafi orientati e non.

• L'algoritmo costruisce un sottografo dei predecessori sui nodi visitati, che in genere è una "depth

first forest"

• L'algoritmo assegna ad ogni nodo due timestamps:

1. v.d = discovery = prima scoperta

2. v.f = finish = fine visita

DFS(G) G,V

For each vertex w

w.color = white

w.p = NULL

time=0 //Timestamp

G,V

For each vertex w

If w.color = white //riporto con nuova sorgente

DFS_VISIT(G,w)

DFS_VISIT(G,w)

Time=time+1

w.d = time

w.color = GRAY

For each v G.Adj[w]

If v.color == WHITE

v.p = w

DFS_VISIT(G,v)

w.color = BLACK

time = time + 1

w.f = time

Il costo dell'operazione di DFS

Il grafo definito dalla variabile v.p definita dalla DFS è una foresta di alberi e riflette la struttura delle

chiamate ricorsive della DFS_VISIT

v.p = w SE E SOLO SE DFS_VISIT(v) è stata invocata durante il ciclo di scorrimento di G.Adj[w]

Inoltre, v è discendente di w solo se v è stato scoperto mentre w era grigio.

I tempi v.d, e v.f sono molto utili poiché possono fornire informazioni sulla topologia del grafo ed i

rapporti di parentela nell'albero dfs:

1. Se w.d, w.f e v.d, v.f sono completamente disgiunti, i due nodi non hanno alcun rapporto di

parentela Algoritmi e strutture dati Pagina 29

parentela

2. Se w.d, w.f è interamente contenuto in v.d, v.f, allora w è discendente di v

3. Se v.d, v.f è interamente contenuto in w.d, w.f allora v è discendente di v

Gli archi si dividono nelle seguenti classi:

• Tree edge = sono gli archi della foresta DFS

• Back edge = arco(w,v) che connette w ad un suo antenato v nella sua foresta DFS.

• Forward edge = arco(w,v) che connette w ad un suo discendente v nella foresta DFS. l'arco non è

un tree edge.

• Cross edge = tutti gli altri archi, che collegano nodi nello stesso albero che non sono in relazione

discendente/antenato.

Il colore del nodo v in un arco(w,v) aiuta a stabilire la natura dell'arco:

• Bianco: tree

• Grigio: back

• Nero: forward oppure cross

Ordinamento topologico

l'ordinamento topologico di un grafo orientato aciclico è un ordinamento lineare di tutti i vertici in v

(qualcosa)

Una classica applicazione della DFS per i grafi orientati è la sua composizione in componenti fortemente

connesse, ossia l'insieme massimale di vertici U<=V tale per cui ossia ogni

coppia di vertici è raggiungibile in entrambi i versi.

Per trovare le componenti fortemente connesse, si può costruire G^T (insieme trasposto) degli archi G.

G e G^T hanno le stesso componenti fortemente connesse

Minimum Spanning Tree

Dato un grafo non orientato connesso G(V,E) e una funzione peso W:E->R, si chiama spanning tree T il

sottografo di G tale che T sia un albero e che T connetta tutti i vertici in G.

Un minimum spanning tree è uno spanning tree il cui costo è minimo.

Il costo di uno spanning tree è la somma dei costi dei suoi archi.

Algoritmi e strutture dati Pagina 30

Un cut(S, V-S) di un grafo G(V,E) è una partizione dell'insieme dei vertici del grafo G.

Un arco(u,v) del grafo G attraversa il cut se:

1.

2.

Consideriamo il seguente grafo, con S = {1, 2, 4} e S-V = {3,5}

Possiamo dire con certezza che gli archi (2,3) , (4,5) e (2,5) attraversano il taglio.

Inoltre, consideriamo un insieme : questo insieme rispetta il taglio se nessuno degli archi di A

attraversa il taglio.

Gli algoritmi che servano per calcolare l'MST usano una strategia greedy, ossia, ad ogni passo scelgono

la strategia che in quel momento appare la migliore. (la più "golosa", "avida")

Gli algoritmo che utilizzano questo approccio per risolvere questo problema costruiscono l'albero a

partire da un singolo nodo, scegliendo man mano archi del peso minore possibile.

Prima di scrivere l'implementazione generica, definiamo il safe edge:

Consideriamo un grafo G(V,E) ed un taglio (S,V-S). Ed un insieme A di archi che rispetta le proprietà di

un MST.

Allora se abbiamo un arco (u,v) di peso minimo che attraversa il taglio, possiamo chiamare quest'arco

arco sicuro (safe edge) poiché aggiungendo l'arco ad A l'insieme A rispetta comuqnue le proprietà di un

MST. Algoritmi e strutture dati Pagina 31

Ora scriviamo l'algoritmo generico per un MST.

Generic MST(G,w)

A = NULL

While A non forma un albero di connessione

Trova un arco (u,v) che è sicuro per A

A = A UNIONE {(u,v)}

Return A

Il criterio per selezionare gli archi che devono fare parte del MST è chiamato MST-property.

l'algoritmo generico mostrato prima sfrutta questa proprietà nella scelta, ad ogni passo, dell'arco da

aggiungere ad A.

Algoritmo di Kruscal

Partendo dall'algoritmo generico greedy aggiunse l'idea di isolare tutti i vertici del grafo, formando una

foresta di alberi disgiunti formati da un singolo vertice. Partendo da ciò vengono considerati

iterativamente tutti gli archi del grafo in ordine di peso crescente, e di applicare la seguente regola:

Se i vertici dell'arco non appartengono allo stesso albero allora unisci i due alberi, altrimenti ignora

l'arco

L'algoritmo quindi terminerà quando la foresta sarà costituita da un singolo albero.

MST_KRUSCAL(G,w)

A = NULL

For each vertex v in V

MAKE_SET(v) //crea un insieme in cui include v

Sort the edges of G.E in non_decreasing order by weight w

For each edge (u,v) in G.E taken in non_decreasing order by weight w

If FIND_SET(w) != FIND_SET(v)

A = A u {(u,v)}

UNION(w,v) //unisce gli insiemi

Return A

Il costo dell'algoritmo dipende dalla struttura dati impiegata per rappresentare gli insiemi di vertici, e

dall'algoritmo di ordinamento:

Algoritmo di Prim

Guarda appunti: taglio Algoritmi e strutture dati Pagina 32

MST_PRIM(G, w, R)

A = NULL

S = {R}

While S != V do

Sia(w,v) l'arco a peso minimo tale che w in S e v in V-S

A = A u {(w,v)}

S = S u {v}

Return A

Esistono diversi modi per implementare la struttura dati che permetta di mantenere ordinati gli archi e

di estrarli agevolmente nell'ordine desiderato: la soluzione migliore è usare le code di priorità (che non

vedremo nel corso quindi cazzocene)

Single source shortest path

• Dato un grafo orientato G(V,E) con associata una funzione peso w : E -> R, il peso di un cammino

p = <v0, v1, v2, vk> è la somma dei pesi dei suoi archi:

• Il peso del cammino minimo da un vertice v ad un vertice w è uguale a:

Il cammino minimo da u a v è un qualsiasi cammino da w a v con peso (scarabocchio)(w,v)

l'algoritmo BFS calcola lo shortest path in un grafo non pesato.

Single source shortest path = dato un grafo orientato G(V,E) ed una funzione peso w : V -> R ed

un nodo sorgente S in V, trovare il cammino minimo da s a ogni altro nodo v in V.

Archi con peso negativo: se il cammino da s a v non contiene cicli con peso negativo, allora il poso

minimo rimane ben definito, anche se eventualmente avrà un valore negativo. Se invece il grafo

contiene cicli negativi, allora per alcuni nodi il peso del cammino minimo non è ben definito:

Algoritmi e strutture dati Pagina 33


ACQUISTATO

1 volte

PAGINE

47

PESO

2.14 MB

AUTORE

sk8erb0y

PUBBLICATO

+1 anno fa


DETTAGLI
Corso di laurea: Corso di laurea magistrale in informatica per la comunicazione
SSD:
Università: Milano - Unimi
A.A.: 2017-2018

I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher sk8erb0y di informazioni apprese con la frequenza delle lezioni di Algoritmi e strutture dati e studio autonomo di eventuali libri di riferimento in preparazione dell'esame finale o della tesi. Non devono intendersi come materiale ufficiale dell'università Milano - Unimi o del prof Foresti Sara.

Acquista con carta o conto PayPal

Scarica il file tutte le volte che vuoi

Paga con un conto PayPal per usufruire della garanzia Soddisfatto o rimborsato

Recensioni
Ti è piaciuto questo appunto? Valutalo!

Altri appunti di Corso di laurea magistrale in informatica per la comunicazione

Grafica e Immagini digitali
Appunto
Applicazioni Web e Cloud - Reti, Cloud, SOAP
Appunto
Basi Di Dati
Appunto
Interazione uomo macchina
Appunto