Riassunto Algoritmi e Strutture dati

E’ dunque difficoltoso stimare un costo medio per l’operazione MULTIPOP, essendo il costo

effettivo dell’operazione variabile.

Assegniamo adesso i seguenti costi ammortizzati

POP 2

PUSH 0

MULTIPOP 0

In questa situazione paghiamo 1 per una POP e associamo a ciascun elemento inserito un credito

di 1, avendo un costo ammortizzato superiore a quello effettivo. Al momento di una POP o di una

MULTIPOP (a cui è stato associato un costo nullo e quindi inferiore a quello effettivo) il costo

necessario a rimuovere ciascun elemento è pagato dal credito associato ad esso.

Poichè ad ogni elemento della pila è associato un credito e nella pila c’è sempre un numero non

negativo di piatti, il vincolo sulla non negatività del credito è soddisfatta.

Ciascuna operazione ha un costo ammortizzato di O(1), quindi il costo ammortizzato di una

qualsiasi sequenza di n operazioni è O(n). Essendo esso un limite superiore per il costo effettivo,

una qualsiasi sequenza viene eseguita nel tempo O(n).

TAVOLE DINAMICHE

In alcune applicazioni potrebbe non essere noto a priori quanti elementi dovranno essere

memorizzati in una tavola. Può capitare dunque che alla richiesta di un inserimento la tavola risulti

piena, e si renda necessario quindi l’allocazione di una nuova tavola più grande in cui verranno

copiati tutti i dati (espansione della tavola). Viceversa, a seguito di varie cancellazioni si può

volere, per una questione di efficienza nell’uso della memoria, l’allocazione di una tavola più

piccola in cui verranno copiati tutti i dati da quella precedente (contrazione della tavola). Le tavole

dinamiche utilizzano questo sistema.

Utilizzando l’analisi ammortizzata dimostriamo che una sequenza di n inserimenti e/o cancellazioni

impiega un tempo O(n) con un tempo medio per operazione costante.

Per aiutarci nell’analisi, definiamo il fattore di carico α(T) della tavola come il rapporto tra il

numero di elementi memorizzti e la dimensione della tavola T. Supponiamo inoltre che la tavola

possieda gli attributi T.size (dimensione della tavola), T.num (numero di elementi memorizzati) e

T.table (tavola effettiva in cui sono memorizzati i dati).

Analizziamo dapprima il solo inserimento. Supponiamo che al momento dell’espansione venga

allocata una nuova tavola di dimensione doppia rispetto all’attuale. Il fattore di carico sarà quindi

sempre maggiore o uguale a 1/2.

TABLE-INSERT(T, x)

1 if T.size == 0

2 alloca T.table con una cella

3 T.size = 1

4 if T.num == T.size

5 alloca new-table con 2*T.size celle

6 inserisci tutti gli elementi di T.table in new-table

7 rilascia T.table

8 T.table = new-table

9 T.size = 2*T.size

10 inserisci x in T.table

11 T.num = T.num + 1

Analizziamo il costo di una sequenza di n inserimenti in funzione degli inserimenti elementari (gli

inserimenti eseguiti nelle righe 6 e 10).

Il costo dell’inserimento nel caso peggiore (inserimento a tavola piena con conseguente

espansione) è funzione lineare del numero di elementi presenti nella tavola, e ciò porterebbe a

2

pensare che il costo di n operazioni di inserimento sia O(n ). Tuttavia il limite non è stretto perché

l’espansione non si può verificare ad ogni inserimento.

Applichiamo il metodo degli accantonamenti attribuendo un costo ammortizzato pari a 3 per ogni

inserimento. Al momento dell’inserimento, un elemento paga 1 per l’inserimento stesso, 1 per il

suo futuro spostamento nella nuova tavola al momento dell’espansione ed 1 per lo spostamento di

un elemento già presente nella tavola. Prendiamo in considerazione una tavola di dimensione m

appena espansa: essa possiede m/2 elementi ed un credito pari a 0. Ogni inserimento aumenta il

credito di 2, ed essendo possibili altri m/2 inserimenti, la tavola piena avrà un credito pari a m.

Dato che la successiva espansione richiederà il trasferimento degli m elementi in una nuova

tavola, il costo per tale operazione può essere coperto interamente dal credito.

Ogni inserimento ha quindi un costo ammortizzato di O(1) da cui deriva un costo per una

sequenza pari a O(n).

Passiamo adesso ad analizzare una tavola su cui vengono effettuati inserimenti e cancellazioni.

Supponiamo che il fattore di carico si mantenga maggiore o uguale a 1/2: inserimenti a seguito di

una contrazione o cancellazioni a seguito di un’espansione causerebbero allocazioni consecutive

di nuove tavole, con la conseguenza che determinate sequenze di operazioni vengono eseguite

2

nel tempo O(n ).

Per ovviare a ciò possiamo permettere a α di scendere sotto 1/2, ad esempio decidendo di

contrarre la tavola quando diventa minore di 1/4. L’analisi ammortizzata dimostra che il costo di n

operazioni di inserimento e cancellazione è O(n), con un costo costante per operazione.

ALBERI BINARI DI RICERCA

Consideriamo un albero binario in cui ogni nodo contiene, oltre a una chiave e ai relativi dati

satelliti, gli attributi left (che indica il figlio sinistro del nodo), right (che indica il figlio destro) e p (che

indica il padre). Ciascuno di questi attributi può contenere il valore NIL se il nodo non ha un figlio o

il padre. Il nodo radice (root) è l’unico nodo in cui p == NIL.

Un albero binario di ricerca è un albero binario sopra descritto in cui ogni chiave rispetta la

proprietà degli alberi binari di ricerca:

Sia x un nodo dell’albero binario di ricerca. Se y è un nodo nel sottoalbero sinistro di x,

y.key <= x.key. Se y è un nodo nel sottoalbero destro di x, y.key >= x.key.

ATTRAVERSAMENTI

Attraversare un albero significa stampare ogni nodo dell’albero. Esistono tre tipi di

attraversamento:

Simmetrico (inorder): per ogni nodo x, vengono stampati prima tutti i nodi nel sottoalbero

• sinistro di x, poi x stesso, ed infine tutti i nodi nel sottoalbero destro.

Anticipato (preorder): viene stampato prima x, poi tutti i nodi nel suo sottalbero sinistro,

• infine tutti i nodi nel sottoalbero destro.

Posticipato (postorder): vengono stampati tutti i nodi nel sottoalbero sinistro di x, poi tutti

• quelli nel sottoalbero destro ed infine x.

La proprietà degli alberi binari di ricerca consente di elencare in ordine crescente le chiavi

effettuando una visita simmetrica (nello specifico chiamando INORDER-TREE-WALK(T.root)).

INORDER-TREE-WALK(x)

1 if x != NIL

2 INORDER-TREE-WALK(x.left)

3 stampa x

4 INORDER-TREE-WALK(x.right)

Poichè INORDER-TREE-WALK ad ogni livello di ricorsione impiega un tempo costante per il

controllo e la stampa del nodo, e richiama sé stesso esattamente due volte, il tempo di esecuzione

su un albero di n nodi è pari a Θ(n).

INTERROGAZIONI

Le interrogazioni di ricerca, minimo, massimo, successore e predecessore possono essere

eseguite nel tempo O(h) in un ABR di altezza h.

Ricerca

Cerca un nodo con chiave k nell’albero. Se la chiave non è presente restituisce NIL.

TREE-SEARCH(x, k) ITERATIVE-TREE-SEARCH(x, k)

1 if x == NIL or x.key == k 1 while x != NIL or x.key != k

2 return x 2 if k < x.key

3 if k < x.key 3 x = x.left

4 return TREE-SEARCH(x.left, k) 4 else x = x.right

5 else return TREE-SEARCH(x.right, k) 5 return x

La procedura esamina dall’alto verso il basso, formando un cammino semplice discendente dalla

radice, quindi il tempo di esecuzione è O(h) in un albero di altezza h.

Minimo e massimo

Restituiscono rispettivamente l’elemento con chiave minima e l’elemento con chiave massima

nell’albero. Per la proprietà degli ABR, l’elemento con chiave minima può essere trovato seguento

il cammino determinato dai puntatori left dei nodi; analogamente, l’elemento con chiave massima

può essere trovato seguento i puntatori right dei nodi.

TREE-MINIMUM(x) TREE-MAXIMUM(x)

1 while x.left != NIL 1 while x.left != NIL

2 x = x.left 2 x = x.left

3 return x 3 return x

La sequenza dei nodi incontrati forma un cammino semplice dalla radice a una foglia, pertanto il

tempo di esecuzione è O(h) in un albero di altezza h.

Successore e predecessore

Dato un nodo x, se l’albero contiene chiavi distinte la seguente procedura restituisce il successore

di x, ossia il nodo con chiave immediatamente successiva a x.key nell’ordine determinato da una

visita simmetrica. Restituisce invece NIL se x è il nodo con chiave massima.

TREE-SUCCESSOR( x)

1 if x.right != NIL

2 return TREE-MINIMUM(x.right)

3 y = x.p

4 while y != NIL and x == y.right

5 x = y

6 y = y.p

Se il sottoalbero destro di x non è vuoto (riga 2), allora il successore di x coincide con il minimo di

quel sottoalbero (riga 3). Altrimenti se x possiede un successore y, y sarà l’antenato più prossimo a

x il cui figlio sinistro è anche antenato di x.

L’esecuzione dell’algoritmo traccia un percorso semplice dal nodo a una foglia o dal nodo alla

radice, a seconda della situazione in cui ci troviamo; di conseguenza il suo tempo di esecuzione è

O(h) in un albero di altezza h.

Il calcolo del predecessore è simmetrico.

INSERIMENTO

L’operazione di inserimento inserisce un elemento z nell’albero, assicurando che la proprietà degli

alberi binari venga rispettata. Traccia un cammino semplice dalla radice confrontando z.key con le

chiavi dei nodi che incontra, fino a trovare una posizione con valore NIL da sostituire con z.

Mantiene inoltre un puntatore inseguitore y per tener traccia del padre del nuovo nodo.

L’operazione viene eseguita nel tempo O(h) in un albero di altezza h.

TREE-INSERT(T, z)

1 y = NIL

2 x = T.root

3 while x != NIL

4 y = x

5 if(z.key<= x.key)

6 x = x.left

7 else

8 x = x.right

9 z.p = y

10 if y == NIL

11 T.root = z

12 else if z.key <= y.key

13 y.left = z

14 else y.right = z

CANCELLAZIONE

L’operazione di cancellazione di un nodo z dall’albero distingue quattro casi:

se z non ha un figlio sinistro, sostituiamo z con il suo figlio destro. Se il figlio destro è NIL

• stiamo considerando il caso in cui z non ha figli.

Se z ha un solo figlio, il sinistro, sosituiamo z con esso.

• Se z ha entrambi i figli dovrà essere sostituito col suo successore y, che si troverà nel

• sottoalbero destro. Si presentano quindi due casi:

y è il figlio destro di z; essendo y il successore di z, non può avere figli sinistri, per cui

◦ basta sostituire y a z, lasciando invariato il sottoalbero destro

altrimenti y si trova nel sottoalbero destro di z, ma non è il suo figlio destro; sostituiamo

◦ y con il suo (unico) figlio destro e poi sostituiamo z con y

Per spostare alberi all’interno di un ABR ci avvaliamo della seguente procedura ausiliaria, che

trapianta il sottoalbero con radice in v al posto del sottoalbero con radice in u:

TRANSPLANT(T, u, v)

1 if u.p == NIL

2 T.root = v

3 else if u == u.p.left

4 u.p.left = v

5 else u.p.right = v

6 if v != NIL

7 v.p = u.p

TREE-DELETE(T, z)

1 if z.left == NIL

2 TRANSPLANT(T, z, z.right)

3 else if z.right == NIL

4 TRANSPLANT(T, z, z.left)

5 else y = TREE-MINIMUM(T, z)

6 if y != z.right

7 TRANSPLANT(T, y, y.right)

8 y.right = z.right

9 y.right.p = y

10 TRANSPLANT(T, z, y)

11 y.left = z.left

12 y.left.p = z.p

La procedura di cancellazione implementa alla lettera i quattro casi presentati sopra. Dato che ogni

operazione impiega un tempo costante, tranne la chiamata a TREE-MINIMUM che impiega O(h),

TREE-DELETE viene eseguito nel tempo O(h).

ABR COSTRUITI IN MODO CASUALE

Tutte le operazioni su di un ABR richiedono un tempo di esecuzione proporzionale all’altezza h

dell’albero. Tuttavia l’altezza dipende dall’ordine in cui vengono inseriti o cancellati gli elementi, ed

un albero di n elementi può arrivare ad avere altezza n-1 se gli elementi sono inseriti ad esempio

in ordine crescente o decrescente, causando tempi di esecuzione molto alti.

Un albero binario di ricerca costruito in modo casuale è un ABR costruito tramite l’inserimento

di n elementi in ordine casuale, dove cioè ciascuna delle n! permutazioni delle chiavi in input ha la

stessa probabilità di essere inserita. L’altezza attesa di un albero di questo tipo è pari a O(lg(n))

quando le chiavi sono distinte.

ALBERI ROSSO-NERI

Un albero rosso-nero è un ABR in cui ad ogni nodo viene associato un bit che ne indica il colore

(rosso o nero). Imponendo vincoli sul colore dei nodi durante un inserimento, un albero rosso-nero

garantisce che ogni cammino dalla radice a una foglia non sia lungo più del doppio di qualsiasi

altro cammino.

Gli alberi rosso-neri rappresentano un modo per bilanciare gli ABR e garantiscono quindi

garantire buoni tempi di esecuzione delle operazioni (ricordiamo che dipendono linearmente

dall’altezza dell’albero).

Un albero rosso-nero è un ABR che soddisfa le seguenti proprietà:

1. Ogni nodo è rosso o nero.

2. La radice è nera.

3. Ogni foglia è nera.

4. Se un nodo è rosso, i suoi due figli sono neri.

5. Per ogni nodo, tutti i cammini semplici che vanno dal nodo a una foglia contengono lo

stesso numero di nodi neri.

Diversamente dagli ABR, indichiamo con “foglia” il valore NIL, e per comodità creiamo un nodo

sentinella T.nil che sostituirà tutti i riferimenti a NIL (compreso il padre della radice) in un classico

ABR.

Definiamo altezza nera di un nodo x (bh(x)) il numero di nodi neri in un qualsiasi cammino da x

(escluso) a una foglia. Dimostriamo adesso il seguente lemma:

Un albero rosso-nero con n nodi interni ha altezza massima pari 2*lg(n + 1).

Dimostriamo inizialmente, per induzione sull’altezza, che un sottoalbero con radice in x ha almeno

bh(x)

2 – 1 nodi interni: 0

Se l’altezza di x è 0, x è una foglia (T.nil) e il sottoalbero con radice in x ha esattamente 2 –

• 1 = 0 nodi interni.

Se bh(x) è positiva, x avrà due figli, ciascuno con altezza nera pari a bh(x) o bh(x) – 1 a

• seconda che sia rosso oppure nero. Essendo l’altezza di un figlio minore dell’altezza di x,

bh(x) – 1

possiamo appliccare l’ipotesi induttiva e dire che ogni figlio ha almeno 2 – 1 nodi

bh(x) – 1 bh(x)

interni. Il sottoalbero con radice in x avrà dunque almeno 2*(2 – 1) + 1 = 2 – 1 nodi

interni, e la tesi è dunque dimostrata.

Indichiamo adesso con h l’altezza dell’albero rosso-nero. Per la proprietà 4 degli alberi rosso-neri,

la radice dell’albero avrà altezza nera almeno pari a h/2, perciò il numero di nodi interni all’albero n

h/2

sarà maggiore o uguale a 2 – 1. Ricavando h:

lg (n+1)≥h /2

h≤2∗lg(n+1)

ed il lemma è dimostrato.

Le operazioni viste per gli ABR (ricerca, massimo, minimo, successore e predecessore) vengono

quindi eseguite nel tempo O(lg(n)) su di un albero rosso-nero.

Gli inserimenti e le cancellazioni devono però essere modificate in modo che le proprietà degli

alberi rosso-neri siano preservate.

ROTAZIONI

L’operazione di rotazione modifica la struttura dell’albero intorno a due nodi x e y preservando le

proprietà degli alberi rosso-neri. È usata come procedura ausiliaria per inserire o cancellare

correttamente un nodo. x

y LEFT-ROTATE(T, x)

γ α y

x β γ

RIGHT-ROTATE(T, x)

β

α

La seguente procedura per una rotazione sinistra suppone x.right != T.nil.

LEFT-ROTATE(T, x)

1 y = x.right

2 x.right = y.left

3 if y.left != T.nil

4 y.left.p = x

5 y.p = x.p

6 if x.p == T.nil

7 T.root = y

8 else if x == x.p.left

9 x.p.left = y

10 else x.p.right = y

11 y.left = x

12 x.p = y

Il codice per RIGHT-ROTATE è simmetrico. Entrambe le procedure vengono eseguite nel tempo

O(1).

INSERIMENTO

È possibile effettuare un inserimento in un albero rosso-nero in un tempo O(lg(n)) utilizzando una

versione modificata della procedura di inserimento in un ABR.

Si inserisce un nodo z nell’albero in maniera analoga a quanto viene fatto in un ABR, solo che

coloriamo questo nodo di rosso: ciò potrebbe violare le proprietà degli alberi rosso-neri, perciò

viene richiamata una procedura ausiliaria RB-INSERT-FIXUP che, tramite rotazioni e cambi di

colore dei nodi, le ripristina.

RB-INSERT(T, z)

1 y = T.nil

2 x = T.root

3 while x != T.nil

4 y = x

5 if z.key <= x.key

6 x = x.left

7 else x = x.right

8 z.p = y

9 if y == T.nil

10 T.root = z

11 else if z.key <= y.key

12 y.left = z

13 else y.right = z

14 z.left = T.nil

15 z.right = T.nil

16 z.color = RED

17 RB-INSERT-FIXUP(T, z)

RB-INSERT-FIXUP(T, z)

1 while z.p.color == RED

2 if z.p == z.p.p.left

3 y = z.p.p.right

4 if y.color == RED

5 z.p.color = BLACK

6 y.color = BLACK

7 z.p.p.color = RED

8 z = z.p.p

9 else if z == z.p.right

10 z = z.p

11 LEFT-ROTATE(T, z)

12 z.p.color = BLACK

13 z.p.p.color = RED

14 RIGHT-ROTATE(T, z.p.p)

15 else (come la clausola then con “right” e “left” scambiati)

16 T.root.color = BLACK

Le uniche due proprietà che possono essere violate a seguito di un inserimento sono la 2 e la 4:

entrambe potrebbero essere violate perché z viene colorato di rosso; la violazione della 2 si

presenta se z viene inserito come radice, la violazione della 4 quando invece z è figlio di un nodo

rosso.

Dimostriamo la correttezza della procedura FIXUP (e quindi dell’intero inserimento) tramite la

seguente invariante di ciclo:

All’inizio di ogni iterazione del ciclo while:

a) Il nodo z è rosso

b) Se z.p è la radice, allora z.p è nero

c) Se ci sono violazioni delle proprietà degli alberi rosso-neri, al massimo ce n’è una e può

riguarda la proprietà 2 o la 4. Se c’è una violazione della proprietà 2, si verifica perché z

è la radice ed è rosso. Se c’è una violazione della proprietà 4, essa si verifica perché z

e z.p sono rossi.

Inizializzazione: prima della prima iterazione del ciclo, T è un albero rosso-nero senza

• violazioni cui è stato aggiunto un nodo rosso. Dimostriamo l’invariante punto per punto:

a. Il nodo z è il nodo appena inserito, quindi è rosso.

b. Se z.p è la radice l’inserimento non ne cambia il colore, e quindi prima della prima

iterazione è sicuramente nero.

c. Violazioni delle proprietà 1, 3 e 5 non possono sicuramente esserci.

Se c’è una violazione della proprietà 2, allora la radice rossa deve essere il nodo z

appena inserito. L’inserimento al posto della radice setta i figli ed il padre di z a T.nil,

perciò non ci sono violazioni della proprietà 4.

Se c’è una violazione della proprietà 4, essa può avvenire solo nel caso in cui z.p è

rosso, perché i figli di z vengono settati a T.nil durante l’inserimento. Non ci sono

violazioni della proprietà 2 perché l’albero non conteneva violazioni prima

dell’inserimento.

Conclusione: Quando il ciclo termina, z.p è nero, quindi non ci sono violazioni della

• proprietà 4. L’unica violazione può riguardare la 2, che viene però ripristinata dall’ultima

istruzione della procedura. In conclusione, al termine di RB-INSERT-FIXUP ‘albero T

rispetta tutte le proprietà degli alberi rosso-neri

Conservazione: ***MANCANTE***

•

STRUTTURE DATI AUMENTATE

A volte si rende necessario modificare strutture dati esistenti, memorizzandovi informazioni

aggiuntive o dotandole di nuove operazioni, per adattarle a specifiche applicazioni. Così facendo

stiamo aumentando la struttura dati.

ALBERO PER STATISTICHE D’ORDINE

Si tratta di un albero rosso-nero che permette di ricavare facilmente informazioni relative alla

statistica d’ordine associata ad ogni nodo.

L’i-esima statistica d’ordine di un insieme di n elementi, con i appartenente a {1, 2, … n}, è

l’elemento dell’insieme con la i-esima chiave più piccola. Il rango di un elemento è invece la

posizione che esso occupa all’interno della sequenza ordinata degli elementi dell’insieme.

Nelle strutture dati ordinarie tali dati possono essere ricavati nel tempo O(n), in un albero per

statistiche d’ordine possono essere ricavati in O(lg(n)).

Esso è un albero rosso-nero in cui ogni nodo x ha un attributo aggiuntivo x.size, che indica il

numero di nodi interni contenuti nel sottoalbero con radice in x (incluso x stesso). Se definiamo

T.nil.size = 0, allora vale la seguente relazione:

x.size = x.left.size + x.right.size + 1

Vediamo le due operazioni aggiuntive definite in un albero per statistiche d’ordine.

Ricerca di un elemento con un dato rango

Restituisce un puntatore al nodo che contiene l’i-esima chiave più piccola (restituisce cioè l’i-esima

statistica d’ordine).

OS-SELECT(x, i)

1 r = x.left.size + 1

2 if r == i

3 return x

4 else if i < r

5 return OS-SELECT(x.left, i)

6 else return OS-SELECT(x.right, i – r)

Poichè ad ogni ricorsione si scende di un livello nell’albero, e l’altezza di un albero rosso nero con

n nodi interni è O(lg(n)), il tempo di esecuzione è O(lg(n)).

Calcolo del rango di un dato elemento

Dato un elemento x restituisce la posizione di x all’interno dell’ordinamento lineare determinato da

una visita simmetrica dell’albero (cioè il suo rango).

OS-RANK(T, x)

1 r = x.left.size + 1

2 y = x

3 while y != T.root

4 if y == y.p.right

5 r = r + y.p.left.size + 1

6 y = y.p

7 return r

Il rango di x può essere visto come il numero di elementi che precede x in una visita simmetrica +

1 per x stesso. Dimostriamone la correttezza usando la seguente invariante di ciclo:

All’inizio di ogni iterazione del ciclo while, r è il rango di x.key nel sottoalbero con radice in y.

Inizializzazione: Prima della prima iterazione, r è il rango di x nel sottoalbero con radice in

• x. L’assegnazione nella riga 2 rende vera l’invariante.

Conservazione: Dato che alla riga 6 viene effettuata l’assegnazione y = y.p, dobbiamo

• dimostrare che se r è il rango di x nel sottoalbero con radice in y all’inizio dell’iterazione, r

sarà il rango di x nel sottoalbero con radice in y.p alla fine dell’iterazione. Se y è figlio

sinistro di suo padre, nessun elemento precede x in una visita simmetrica e quindi

lasciando r invariato l’invariante è conservata. Se invece y è figlio destro di suo padre, tutti i

nodi nel sottoalbero sinistro di y.p e y.p stesso precedono x in una visita simmetrica: la riga

5 aggiorna di conseguenza r e l’invariante è dimostrata.

Conclusione: Alla fine del ciclo, y = T.root quindi r è il rango di x all’interno dell’intero

• albero. L’algoritmo è corretto.

Il tempo di esecuzione è O(lg(n)).

Gestione dell’attributo size su inserimento

L’attributo size dei nodi dell’albero deve essere tenuto aggiornato a seguito di ogni inserimento, e

la procedura di aggiornamento non deve influire sul costo asintotico dell’inserimento stesso.

L’inserimento in un albero rosso-nero si compone di due fasi: discesa dalla radice a una foglia per

inserire il nuovo nodo, e risalita dal nuovo nodo alla radice nella procedura RB-INSERT-FIXUP,

effettuando rotazioni e cambi di colore.

Durante la prima fase basta incrementare l’attributo size di ogni nodo che incontriamo durante il

cammino semplice discendente. Effettuiamo O(lg(n)) incrementi con un costo pari a O(1), quindi il

costo totale per l’aggiornamento in questa fase è O(lg(n)), asintoticamente uguale a quello

dell’inserimento.

Durante la seconda fase, le modifiche strutturali sono dovute alle rotazioni. Una rotazione è però

un’operazione locale, che coinvolge due nodi x e y, perciò dovranno essere aggiornati solo gli

attributi size di questi due. Con riferimento alla procedura LEFT-ROTATE(T, x) dobbiamo

modificare gli attributi nel seguente modo:

y.size = x.size

x.size = x.left.size + x.right.size + 1

Poichè vengono effettuate al massimo due rotazioni il costo dell’aggiornamento in questa fase è

O(1).

L’aggiornamento di size non inficia quindi il tempo di esecuzione dell’inserimento.

ALBERI DI INTERVALLI

Potrebbe rendersi necessario l’utilizzo di una struttura dati per la memorizzazione e la gestione di

intervalli. Un intervallo [t , t ] può essere visto come un oggetto i avente gli attibuti i.low = t

1 2 1

(estremo inferiore) e i.high = t (estremo superiore). Dati due intervalli i e i’ essi soddisfano la

2

tricotomia degli intervalli, ovvero solo una delle seguenti proprietà può essere vera:

i e i’ si sovrappongono (i’.low <= i.high e i.low <= i’.high)

• i è a destra di i’ (i.low > i’.high)

• i è a sinistra di i’ (i.high < i’.low)

•

Un albero di intervalli è un albero rosso-nero che gestisce un insieme dinamico di intervalli;

vediamone le caratteristiche.

Struttura dati base: consideriamo un albero rosso-nero in cui ogni elemento x possiede

• l’attributo x.int che rappresenta l’intervallo associato. La chiave dell’elemento è l’estremo

inferiore dell’intervallo, x.int.low, perciò una visita simmetrica elenca ordinatamente gli

intervalli in funzione dell’estremo inferiore.

Informazioni aggiuntive: oltre all’intervallo, ogni nodo x possiede l’attributo x.max, che

• rappresenta il massimo estremo superiore di tutti gli intervalli memorizzati nel sottoalbero

con radice in x.

Gestione delle informazioni: dobbiamo verificare che la gestione delle informazioni

• aggiuntive non aumentino il tempo di esecuzione di inserimento e cancellazione. L’unico

attributo da tenere aggiornato è x.max, nel seguente modo:

x.max = max(x.left.max, x.right.max, x.int.high)

cioè nel tempo O(1). Quindi inserimento e cancellazione vengono eseguiti sempre nel

tempo O(lg(n)).

Sviluppare le nuove operazioni: l’unica nuova operazione da introdurre è la ricerca di un

• nodo il cui intervallo si sovrappone a un intervallo i dato in input.

Sviluppiamo dunque la nuova procedura:

INTERVAL-SEARCH(T, i)

1 x = T.root

2 while x != T.nil and x.int non si sovrappone ad i

3 if x.left != T.nil and x.left.max >= i.low

4 x = x.left

5 else x = x.right

6 return x

La procedura restituisce il nodo contenente un intervallo che si sovrappone ad i, oppure T.nil se

nell’albero non esiste un intervallo del genere. Nel ciclo while viene tracciato un cammino semplice

dalla radice, ed ogni iterazione impiega un tempo costante, perciò il tempo di esecuzione di

INTERVAL-SEARCH è O(lg(n)).

Dimostriamo la correttezza attraverso la seguente invariante di ciclo per il ciclo while (riga 2):

Se l’albero T contiene un intervallo che si sovrappone a i, allora un tale intervallo esiste nel

sottoalbero con radice in x.

Inizializzazione: prima della prima iterazione x è la radice dell’albero T, perciò l’invariante è

• vera.

Conservazione: Dimostriamo che l’invariante si conserva in entrambi i casi considerati

• durante un’iterazione.

Se viene eseguita la riga 5, allora x.left == T.nil o x.left.max < i.low. Se x.left == T.nil x.left è

vuoto e ovviamente non può contenere un intervallo che si sovrappone a i. Se invece

x.left.max < i.low significa che per ogni intervallo i’ contenuto nel sottoalbero con radice in

x.left si ha i’.high < i.low e per la tricotomia degli intervalli nessun i’ si sovrappone a i. Il

sottoalbero sinistro di x non può dunque contenere l’intervallo cercato, e ponendo

x = x.right si conserva l’invariante.

Se viene eseguita la riga 4 allora x.left.max >= i.low, e quindi esiste un intervallo i’ nel

sottoalbero sinistro di x tale che i’.high >= i.low. L’intervallo i si sovrapporrà a i’ solo se

i’.low <= i.high. Poichè l’albero di intervalli utilizza gli estremi inferiori come chiavi, se esiste

un intervallo i’ che si sovrappone ad i esso può trovarsi solo nel sottoalbero sinistro di x.

Ponendo x = x.left si mantiene l’invariante.

Conclusione: Quando il ciclo termina, x contiene il nodo il cui intervallo si sovrappone ad i,

• oppure il nodo T.nil se l’albero non contiene tale intervallo. La procedura è dunque corretta.

B-ALBERI

Sono ABR bilanciati progettati per operare bene sulla memoria secondaria, ossia ogni operazione

è ottimizzata per ridurre al minimo le operazioni di I/O. Sono tipicamente usati nei database.

La memoria secondaria (tipicamente dischi magnetici) hanno tempi di accesso, lettura e scrittura

molto più alti rispetto alla memoria principale. Quando si opera su di essa dobbiamo ridurre al

minimo gli accessi alla memoria, perciò la nostra analisi sul costo di un algoritmo su una struttura

dati in memoria secondaria sarà fatta in funzione non solo del tempo di calcolo della CPU, ma

anche del numero di accessi al disco (più precisamente, del numero di pagine lette o scritte).

La applicazioni che usano B-Alberi si trovano a gestire una tale quantità di dati che rende

impossibile il loro mantenimento nella memoria principale. Questa particolare struttura dati

garantisce perciò che in ogni istante siano presenti nella memoria principale solo un numero

costante di pagine del disco. Ciò significa che la dimensione di un B-Albero è limitata solo dalla

dimensione della memoria secondaria, ma anche che esso deve occuparsi del caricamento delle

pagine da disco, e la riscrittura su di esso delle pagine modificate.

A differenza di un albero rosso-nero, ogni nodo del B-Albero può avere più di due figli. Faremo

l’ipotesi che se un oggetto x del B-Albero si trova in memoria principale, allora possiamo accedere

ai suoi attributi, altrimenti dobbiamo caricarlo dalla memoria secondaria tramite l’istruzione DISK-

READ(x) (che non farà nulla se x è già stato caricato). A seguito della modifica di x, dobbiamo

aggiornare il suo valore in memoria secondaria tramite l’istruzione DISK-WRITE(x). Si suppone

inoltre che ogni nodo corrisponda a una pagina del disco.

Diamo una definizione di B-Albero. Esso è un albero con le seguenti proprietà:

1. Ogni nodo x ha i seguenti attributi:

a. x.n, che corrisponde al numero di chiavi memorizzate nel nodo

b. Le x.n chiavi, x.key , x.key , … x.key , memorizzate in ordine non decrescente

1 2 x.n

c. x.leaf, un booleano che indica se x è una foglia

2. Ogni nodo possiede x.n + 1 figli, i cui puntatori memorizzati negli attributi x.c , x.c , … x.c .

1 2 n+1

I nodi foglia non hanno figli quindi i relativi attributi non sono definiti.

3. Le chiavi x.key definiscono gli intervalli per le chiavi memorizzate nei sottoalberi dei figli.

i

Sia k una chiave contenuta in un sottoalbero con radice in c [x], allora

i i

k <= x.key <= k <= x.key <= … <= x.key <= k

1 1 2 2 x.n n+1

4. Tutte le foglie hanno la stessa profondità, che è l’altezza h dell’albero.

5. Ci sono limiti superiori e inferiori al numero di chiavi memorizzate in ciascun nodo. Definito

un intero t >= 2 detto grado dell’albero:

a. Ogni nodo, tranne la radice, deve avere almeno t – 1 chiavi. Ogni nodo tranne la radice

ha quindi almeno t figli

b. Ogni nodo può contenere al massimo 2t – 1 chiavi, quindi un nodo può avere al

massimo 2t figli. Un nodo si dice pieno se contiene esattamente 2t – 1 chiavi.

Il numero di accessi al disco delle operazioni di un B-Albero è proporzionale all’altezza dell’albero

stesso. Dimostriamo dunque il seguente teorema:

In un B-Albero con n chiavi, n >= 1, altezza h e grado minimo t >= 2, si ha

n+1

h≤log t 2

La radice di un albero di grado minimo t contiene almeno una chiave e ogni nodo contiene almeno

t – 1 chiavi. Alla profondità 1 l’albero ha almeno 2 nodi (perché la radice ha almeno 1 nodo), alla

profondità 2 ha almeno 2t nodi (perché ogni nodo ha almeno t – 1 chiavi e quindi t figli), alla

2

profondità 3 almeno 2t nodi e così via. Alla profondità h (dove h è l’altezza dell’albero) ha almeno

h – 1

2t nodi. Dato n, numero di chiavi memorizzate nell’albero, vale quindi la seguente relazione:

h

∑ i−1

n≥1+(t−1) 2 t

i=1 h

t −1

=1+2(t−1) t −1

h

t

=2 −1

Passando ai logaritmi in base t e isolando h si ottiene la tesi.

Vediamo adesso le operazioni che si possono eseguire sui B-Alberi. Ipotizziamo che la radice si

trovi sempre in memoria: non è quindi necessario effettuare il DISK-READ per questo nodo; in

seguito alla modifica di esso va comunque effettuato un DISK-WRITE. Inoltre, prima di passare un

nodo x come parametro di una procedura, imponiamo di dover eseguire DISK-READ(x).

Ricerca

La ricerca è analoga a quella negli ABR, solo che invece di scegliere tra due alternative, quando

incontriamo il nodo x dobbiamo scegliere tra x.n + 1 alternative per decidere in quale figlio di x

proseguire la ricerca. La procedura restituisce NIL se la chiave cercata non è presente nell’albero,

altrimenti restituisce la coppia (y, i) che sta a indicare che l’elemento richiesto è y.key .

i

B-TREE-SEARCH(x, k)

1 i = 1

2 while i <= x.n and k > x.key i

3 i = i + 1

4 if i <= x.n and k == x.key i

5 return (x, i)

6 else if x.leaf

7 return NIL

8 else DISK-READ(x.c )

i

9 return B-TREE-SEARCH(x.c , k)

i

I nodi incontrati durante la ricorsione formano un cammino semplice discendente. Il tempo di

esecuzione nel ciclo while all’interno di ogni ricorsione è O(t), perciò il tempo di esecuzione della

ricerca è O(t*h) = O(t*log (n)).

t

Creazione di un B-Albero vuoto

Questa procedura creanel tempo O(1) un nuovo B-Albero senza chiavi. Si avvale della procedura

ausiliaria ALLOCATE-NODE() che alloca una pagina sul disco da usare come nuovo nodo.

B-TREE-CREATE(T)

1 x = ALLOCATE-NODE()

2 x.leaf = TRUE

3 x.n = 0

4 DISK-WRITE(x)

5 T.root = x

Inserimento

L’inserimento consiste nella ricerca, a partire dalla radice, della foglia x in cui inserire la nuova

chiave. Se questa foglia risulta piena, dobbiamo però dividere x in corrispondenza della sua chiave

mediana in due nodi, con t – 1 chiavi ciascuno. La chiave mediana viene portata in alto nel padre

di x, e segnerà il punto di divisione tra i due nuovi nodi. Se anche il padre di x risultasse pieno,

andrebbe a sua volta diviso, e questo fenomeno si potrebbe propagare fino alla radice. Per non

dover effettuare due cammini (uno dalla radice alla foglia, e l’altro dalla foglia verso l’alto) durante

l’inserimento dividiamo tutti i nodi pieni che incontriamo.

La seguente procedura riceve in input un nodo x non pieno ed un indice i tale che y = x.c è un

i

nodo pieno. Il nodo y viene diviso in due e x viene modificato in modo da avere un nuovo figlio,

contenente metà chiavi che prima erano in y. Se dobbiamo dividere una radice piena, dobbiamo

prima creare un nuovo nodo radice vuoto, che avrà come figlio l’attuale radice, e poi richiamare la

procedura di suddivisione. Questo è l’unico modo in cui l’altezza del B-Albero può crescere.

B-TREE-SPLIT-CHILD(x, i)

1 z = ALLOCATE-NODE()

2 y = x.c i

3 z.leaf = y.leaf

4 z.n = t – 1

5 for j = 1 to t – 1

6 x.key = y.key

j t + j

7 if not y.leaf

8 for j = 1 to t – 1

9 x.c = y.c

j t + j

10 y.n = t – 1

11 for j = x.n + 1 downto i + 1

12 x.c = x.c

j+1 j

13 x.c = z

i+1

14 for j = x.n downto i

15 x.key = x.key

j+1 j

16 x.key = y.key

i t

17 x.n = x.n + 1

18 DISK-WRITE(x)

19 DISK-WRITE(y)

20 DISK-WRITE(z)

Il tempo utilizzato dalla procedura è Θ(t), mentre le operazioni su disco sono O(1).

Di seguito troviamo il codice per l’inserimento in un singolo passaggio (ossia effettuando un solo

cammino dalla radice a una foglia).

B-TREE-INSERT(T, k)

1 r = T.root

2 if r.n == 2t – 1

3 s = ALLOCATE-NODE()

4 s.n = 0

5 s.leaf = FALSE

6 s.c = r

1

7 T.root = s

8 B-TREE-SPLIT-CHILD(s, 1)

9 B-TREE-INSERT-NON-FULL(s, k)

10 else B-TREE-INSERT-NON-FULL(r, k)

B-TREE-INSERT-NONFULL(x, k)

1 i = x.n

2 if x.leaf

3 while i >= 1 and k < x.key i

4 x.key = x.key

i+1 i

5 i = i - 1

6 x.key = k

i

7 x.n = x.n + 1

8 DISK-WRITE(x)

9 else while i >= 1 and k < x.key i

10 i = i – 1

11 i = i + 1

12 DISK-READ(x.c )

i

13 if x.c .n == 2t – 1

i

14 B-TREE-SPLIT-CHILD(x, i)

15 if k > x.key i

16 i = i + 1

17 B-TREE-INSERT-NONFULL(x.c , k)

i

B-TREE-INSERT prima dell’inserimento vero e proprio controlla se la radice è piena: in tal caso va

creata una nuova radice per poi dividere quella attuale, facendo aumentare l’altezza dell’albero.

In B-TREE-INSERT-NONFULL il blocco di istruzioni dell’if gestisce il caso in cui x sia una foglia: la

chiave k viene opportunamente inserita in x. Se x non è una foglia, dobbiamo cercare il figlio di x in

cui proseguire la ricorsione. Se questo figlio è pieno va prima diviso.

In un albero di altezza h l’inserimento richiede quindi O(h) accessi al disco (O(1) per ogni

ricorsione) e un tempo di esecuzione pari a O(t*h).

PROGRAMMAZIONE DINAMICA

È un metodo di progettazione di algoritmi molto simila a quello divide et impera. Anche in questo

caso ci troviamo a suddividere il problema in più sottoproblemi, risolvere i sottoproblemi e

combinare le soluzioni per determinare la soluzione del problema originale. La programmazione

dinamica tuttavia si applica al caso in cui, nel corso delle ricorsioni, vengano generati

sottoproblemi uguali. In questo contesto il metodo divide et impera risolverebbe più volte gli stessi

sottoproblemi, con un evidente spreco di tempo. La programmazione dinamica memorizza invece

la soluzione di ogni problema incontrato, così da averla a disposizione nel caso si ripresentasse.

È solitamente impiegata nei problemi di ottimizzazione, e si compone di 4 fasi:

1. Caratterizzare la struttura di una soluzione ottima.

2. Definire in modo ricorsivo il valore di una soluzione ottima.

3. Calcolare il valore di una soluzione ottima, solitamente con un approccio bottom-up

4. (Facoltativo) Costruire una soluzione ottima dalle informazioni calcolate.

Un problema di ottimizzazione può essere risolto con il metodo della programmazione dinamica se

possiede due caratteristiche:

Sottostruttura ottima: la soluzione ottima del problema contiene le soluzioni ottime dei

• suoi sottoproblemi

Sottoproblemi ripetuti: l’algoritmo ricorsivo per il problema visita più volte gli stessi

• problemi

Vediamo due esempi di problemi risolti con la programmazione dinamica.

PROBLEMA DEL TAGLIO DELLE ASTE

Data un’asta di lunghezza n pollici e una tabella di prezzi p , i = 1, 2, … n, vogliamo determinare il

i

ricavo massimo r che si può ottenere tagliando l’asta e vendendone i pezzi.

n

Se una soluzione ottima prevede il taglio dell’asta in k parti (1 <= k <= n), allora la decomposizione

ottima n = i + i + … i in pezzi di lunghezza i , i , .. i fornisce il seguente ricavo massimo:

1 2 k 1 2 k

r = p + p + … + p

n i1 i2 ik

Si deduce quindi che possiamo esprimere r in funzione delle aste più corte:

n

r = max(p , r + r , r + r , … r + r )

n n 1 n-1 2 n-2 n-1 1

In questo modo ogni problema è suddiviso in due sottoproblemi. Possiamo eseguire una

semplificazione e far dipende la soluzione r da un solo sottoproblema:

n max

r p

= ( +r )

n i n−i

1≤i≤n

Il taglio delle aste presenta dunque una sottostruttura ottima.

Utilizzando la formula sopra per implementare un algoritmo ricorsivo scopriamo che il problema

presenta inoltre la caratteristica dei sottoproblemi ripetuti (l’algoritmo ha tempo di esecuzione

n

Θ(2 ).

Possiamo dunque utilizzare la programmazione dinamica secondo due approcci:

Metodo top-down con annotazione: si modifica l’algoritmo ricorsivo classico in modo che

• salvi (in un array ad esempio) le soluzioni di ogni sottoproblema risolto. Ad ogni livello di

ricorsione l’algoritmo controlla se ha precedentemente già risolto il sottoproblema in esame:

in caso affermativo restituisce direttamente il valore della soluzione, altrimenti lo risolve e

salva la soluzione.

Metodo bottom-up: risolviamo tutti i sottoproblemi a partire dal più piccolo, salvandone la

• soluzione. Quando incontriamo un particolare problema, abbiamo già risolto i suoi

sottoproblemi e possiamo quindi determinarne la soluzione.

I due metodi generano algoritmi con lo stesso tempo di esecuzione asintotico, ma generalmente il

bootm-up ha fattori costanti migliori. Tuttavia in particolari problemi non è necessario risolvere tutti i

possibili sottoproblemi (come fa il metodo bottom-up), di conseguenza l’approccio top-down può

risultare più vantaggioso.

MEMOIZED-CUT-ROD(p, n)

1 Sia r[0 … n] un nuovo array

2 for i = 0 to n

3 r[i] = -∞

4 return MEMOIZED-CUT-ROD-AUX(p, n, r)

MEMOIZED-CUT-ROD-AUX(p, n, r)

1 if r[n] >= 0

2 return r[n]

3 if n == 0

4 q = 0

5 else q = -∞

6 for i = 1 to n

7 q = max(q, p[i] + MEMOIZED-CUT-ROD-AUX(p, n - i, r))

8 r[n] = q

9 return q

BOTTOM-UP-CUT-ROD(p, n)

1 Sia r[0 … n] un nuovo array

2 r[0] = 0

3 for j = 1 to n

4 q = -∞

5 for i = 1 to j

6 q = max(q, p[i] + r[j – i])

7 r[j] = q

8 return r[n]

Con questi algoritmi abbiamo calcolato il valore della soluzione ottima, ma non la soluzione ottima

in sé. Possiamo modificare la procedura BOTTOM-UP-CUT-ROD in modo che memorizzi in un

array s, per ogni dimensione j dell’asta, la dimensione ottima s del primo pezzo da tagliare per

j

ottenere il ricavo massimo r .

j

PROBLEMA DELLA LCS

Date due sequenze X = <x , x , … x > e Y = <y , y , … y > vogliamo trova una sottosequenza di

1 2 m 1 2 n

lunghezza massima che è comune a X e Y.

Data una sequenza X = <x , x , … x >, un’altra sequenza Z = <z , z , … z > è una sottosequenza

1 2 m 1 2 k

di x se esiste una sequenza strettamente crescente di indici <i , i , … i > di X tali che per ogni j = 1,

1 2 k

2, … k si ha x = z .

ij j

Risolviamo il problema della LCS con la programmazione dinamica. Vediamo una per una le 4 fasi:

1. Caratterizzare la più lunga sottosequenza comune

Data una sequenza X = <x , x , … x > definiamo X = <x , x , … x > l’i-esimo prefisso di X,

1 2 m i 1 2 i

per i = 0, 1, … m. X è la sequenza vuota.

0

Il seguente teorema dimostra che il problema della LCS gode della proprietà della

sottostruttura ottima:

Siano X = <x , x , … x > e Y = <y , y , … y > due sequenze; sia Z = <z , z , … z > una

1 2 m 1 2 n 1 2 k

qualsiasi LCS di X e Y.

1 Se x = y allora z = x = y e Z è una LCS di X e Y .

m n k m n k – 1 m-1 n-1

2 Se x != y allora z != x implica che Z è una LCS di X e Y

m n k m k m-1 .

3 Se x != y allora z != y implica che Z è una LCS di X e Y

m n k n k n-1.

Una LCS di due sequenze ha quindi al suo interno una LCS di prefissi delle due sequenze.

2. Una soluzione ricorsiva

Dal teorema della sottostruttura ottima del problema della LCS si evince che per trovare

una LCS di X e Y potrebbe essere necessario trovare sia una LCS di X e Y sia una di X

m-1

e Y . Entrambi i sottoproblemi avranno il sottosottoproblema di trovare una LCS di X e

n-1 m-1

Y . Intuiamo quindi che il problema gode della proprietà dei sottoproblemi ripetuti.

n-1

Consideriamo quindi una matrice c dove c[i, j] è la lunghezza di una LCS delle sequenze X i

e Y . Se i=0 o j=0 una delle sequenze è vuota quindi la LCS ha lunghezza 0. Possiamo

j

dunque scrivere la seguente formula ricorsiva per il problema della LCS:

se i=0 o j=0

0

{ se i , j e x y

c j]= c j−1]+1 >0 =

[i, [i−1, i j

max( c , j−1], c j se i , j e x != y

[i [i−1, ]) >0 i j

3. Calcolare la lunghezza di una LCS

Usiamo la formula ricorsiva definita nel punto 2 per scrivere il seguente algoritmo

bottom-up. La procedura utilizza e restituisce anche una matrice b che semplifica la

ricostruzione della soluzione ottima.

LCS-LENGHT(x, y)

1 m = X.lenght

2 n = Y.lenght

3 Siano b[1 … m, 1 … n] e c[0 … m, 0 … n] due nuove tabelle

4 for i = 0 to m

5 c[i, 0] = 0

6 for j = 0 to n

7 c[0, j] = 0

8 for i = 1 to m

9 for j = 1 to n

10 if x == y

i j

11 c[i, j] = c[i – 1, j – 1] + 1

↖

12 b[i, j] = “ “

13 else if c[i – 1, j] >= c[i, j -1]

14 c[i, j] = c[i – 1, j]

15 b[i, j] = “↑”

16 else c[i, j] = c[i, j – 1]

17 b[i, j] = “←”

18 return c e b

Il tempo di esecuzione è Θ(m*n) perché il tempo di calcolo per calcolare ogni posizione

della matrice è Θ(1).

4. Ricostruire una LCS

Con la tabella b possiamo ricostruire la soluzione ottima, partendo da b[m, n] e seguendo le

↖

frecce. Ogni volta che incontriamo “ “ nella posizione b[i, j] significa che x = y è un

i j

elemento della LCS. Gli elementi verranno incontrati in ordine inverso.

PRINT-LCS(b, X, i, j)

1 if i == 0 or j == 0

2 return

↖

3 if b[i, j] == “ “

4 PRINT-LCS(b, X, i – 1, j – 1)

5 print x i

6 else if b[i, j] == “↑”

7 PRINT-LCS(b, X, i – 1, j)

8 else

9 PRINT-LCS(b, X, i – 1, j)

GRAFI

Un grafo è una coppia (V, E) dove V è detto insieme dei vertici e E è insieme degli archi. Ogni arco

contenuto in E mette in relazione una coppia di vertici appartenenti a V. Un grafo si dice orientato

se E è composto da coppie di vertici ordinate ( l’arco (u, v) è diverso dall’arco (v, u)), altrimenti il

grafo è non orientato.

Esistono due modi per rappresentare un grafo:

Liste di adiacenza: un grafo G = (V, E) è rappresentato attraverso un array Adj di |V| liste,

• una per ogni vertice. Adj[u] contiene tutti i vertici adiacenti al nodo u, ossia tutti i nodi v tali

che (u, v) appartiene a E. Adj può essere visto come un attributo di G. La memoria richiesta

per memorizzare un grafo con questo metodo è Θ(V + E).

Matrice di adiacenza: un grafo G = (V, E) è rappresentato mediante una matrice A = (a ) di

• ij

dimensione |V|x|V| dove 1 se(i , j)∈E

{

a =

ij 0 altrimenti 2

La matrice di adiacenza impiega una memoria pari a Θ(V ), indipendentemente dal

numero di archi.

La rappresentazione tramite liste di adiacenza è preferibile nel caso di matrici sparse, perché

impiega una quantità minore di memoria; essa presenta però come svantaggio che per

determinare se un arco è presente nel grafo dobbiamo scorrere interamente una lista di adiacenza,

mentre nel caso della matrice di adiacenza l’informazione può essere ricavata immediatamente (si

accede direttamente alla cella relativa a quel particolare arco). La matrice di adiacenza è inoltre

preferita nel caso di grafi piccoli.

Il primo metodo con le liste di adiacenza è comunque il più usato.

VISITA IN AMPIEZZA (BFS)

Dato un grafo G = (V, E) ed un vertice s appartenente a v, detto sorgente, la visita in ampiezza

ispeziona sistematicamente gli archi di G per scoprire tutti i vertici raggiungibili da s. Calcola la

distanza (ossia il numero minimo di archi) da s ad ogni vertice raggiungibile, ed infine genera un

albero BF (detto breadth-first-tree) con radice s e contenente tutti i vertici raggiungibili. Un

cammino da s a un vertice nell’albero BF corrisponde a un cammino minimo tra s ed il vertice

all’interno del grafo.

L’algoritmo ispeziona in successione le liste di adiacenza dei nodi incontrati, a partire dalla

sorgente, e tiene traccia del lavoro svolto colorando i vertici. Inizialmente tutti i vertici (tranne la

sorgente) sono bianchi. Quando un vertice v viene scoperto (ossia viene incontrato per la prima