Riassunto Algoritmi e Strutture dati
Anteprima
ESTRATTO DOCUMENTO
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
I contenuti di questa pagina costituiscono rielaborazioni personali del Publisher gostexo 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à Firenze - Unifi o del prof Marinai Simone.
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