Data Structures

Abstract Data Type

Tipi predefiniti sono forniti dai linguaggi

• ogni tipo é associato con un insieme di valori e operatori

Una implementazione concreta di un ADT é

• struttura dati
• collezione di procedure con cui realizzare le operazioni

La relazione fra tipo astratto e struttura concreta é analoga a quella fra problema algoritmico e algoritmo

Strutture Dati

Insiemi Dinamici

Possibili in array, liste o hash, ma con tempo di calcolo diversi

• elementi finiti
• gli elementi possono cambiare
• il loro numero puó cambiare
• si assume che ogni elemento abbia un attributo chiave
• si assume che le chiavi sono tutte distinte

2 tipi di operazione

• query
• modifiche

tipicamente

• insert
• search
• delete

inoltre hanno senso se l’insieme é ordinato (le chiavi sono ordinate)

• minimum
• maximum
• successor
• predecessor

Strutture dati diverse hanno diversa complessitá con operazioni diverse

• ogni struttura ha efficienza migliore in base a ció che si va a sviluppare

Array

caselle

• contengono un elemento
• sono grandi uguali
• posizionati in una sequenza nella memoria
• il calcolo dell'indirizzo di qualunque casella ho costo costante
  • non dipende dal numero di elementi
  • base + (i-1) * dim(valore)
• accesso diretto
  • \(O(1)\)

Statici

Numero massimo di elementi prefissato

• M: numero massimo
  • non ha impatti sui tempi di calcolo
• N: numero attuale de elementi
  • occupano sempre le prime N celle dell’array

• Insert

  Senza controllo sulla ripetizione di chiave #+begin-example ArrayInsert(A,k): if A.N != A.M A[A.N] = k A.N++ return k else return nil #+end-example \(O(1)\) costante

  Se l’Array é ordinato gli inserimenti costano di piú

  • inserendo k in fondo
  • far scendere alla posizione giusta con scambi (InsertionSort)

  \(O(N)\)

• Delete

  Assumendo non ci siano ripetizioni #+begin-example ArrayDelete(A, k): for i=1 to A.N do if A[i] == k then A.N = A.N + 1 for j=i to A.N do A[j] = A[j+1] return k return nil #+end-example \(O(N)\) lineare

• Search

  #+begin-example ArraySearch(A,k): for i=1 to A.N do if A[i] == k then return k return nil #+end-example \(O(N)\) lineare

  Se l’Array é ordinato allora possiamo implementare la BinarySearch \(O(n \log n)\)

Ridimensionabili / Dinamici

Se non si conosce il numero massimo di elementi a priori Se non si vuole sprecare spazio

Le 2 idee utilizzate sono due soluzioni diverse per la realizzazione di un Abstract Data Type

• per confrontarle valutiamo i tempi di esecuzione di sequenze di operazioni

  • consideriamo allora il costo medio per i confronti: costo ammortizzato
    • costo ammortizzato nel futuro anche se costoso subito

• \(2^k\) inserimenti, con M=1 inizialmente

  1. ogni inserimento tranne il primo ha costo \(O(N)\)
     • \(T_{amm} = \frac{d + c + 2c + … + (n-1)c}{n} \in O(n)\)
       • sopra abbiamo una progressione aritmetica
         • numeratore di secondo grado, denominatore di primo grado
  2. \(k\) inserimenti con \(O(N)\), gli altri \(O(1)\)
     • \(T_{amm}= \frac{(c+2c+…+2^{k-1}c)+2^kd}{2^k}\)
     • \(T_{amm}= \frac{(2^k -1)c+2^kd}{2^k} \in O(1)\)

• sequenza di rimozioni di elementi

• sequenza di inserimenti, ma aumentando la dimensione dell’array di una costante se riempito

• Extend

  Si basa sull’espandere l’array quando esso diventa troppo piccolo

  • l’espansione costa \(O(N)\) in quanto richiede di allocare memoria e copiare gli elementi dell’array

  #+begin-example ArrayExtend(A,n): B = array[A.M + n] B.M = A.M + n B.N = A.N for i=1 to A.N do B[i] = A[i] return B #+end-example

  Il problema é che se N == M allora i successivi inserimenti richiedono ulteriori riallocazioni

• Insert

  #+begin-example DynArrayInsert(A,k): if A.N == A.M then A = ArrayExtend(A,1) ArrayInsert(A,k) #+end-example Array non pieno: \(O(1)\) Array pieno: \(O(N)\) Dipende dalle operazioni precendenti

  • se M é sufficientemente grande si sforeranno poche volte
    • il costo sará circa \(O(1)\) ma si rischia di sprecare spazio
  • se M é tale da sforare molte volte
    • il costo sará circa \(O(N)\)

  Il problema é che se N == M allora i successivi inserimenti richiedono ulteriori riallocazioni

  • raddoppiamo il numero di elementi se l’array si riempie

  #+begin-example DynArrayInsert(A,k): if A.N == A.M then A = ArrayExtend(A,A.M) ArrayInsert(A,k) #+end-example

• Delete

  Possiamo recuperare spazio se l’array si riduce di dimensione #+begin-example DynArrayDelete2(A,k): ArrayDelete(A,k) if A.N <= 1/4 * A.M then B = array[A.M/2] B.M = A.M/2 B.N = A.N for i=1 to A.N do B[i] = A[i] A = B #+end-example

• Search

Liste

Una struttura lineare

• l’ordine é determinato dai puntatori che indicano l’elemento successivo
• data una lista L il primo elemento é indicano da L.head

Puó essere doppiamente concatenata

• con puntatori .prev e .next

Puó essere

• ordinata
• non ordinata

Puó essere circolare

• l’ultimo elemento punta il primo e viceversa
  • permette di accedere all’ultimo elemento piú facilmente

Insert

In Liste doppiamente concatenate e non ordinate: #+begin-example ListInsert(L,x): x.next = L.head x.prev = nil if L.head != nil then L.head.prev = x L.head = x #+end-example \(O(1)\)

Con sentinella: #+begin-example ListInsert(L,x): x.next = L.sen.next L.sen.next.prev = x L.sen.next = x x.prev = L.sen #+end-example \(O(1)\)

Delete

In Liste doppiamente concatenate e non ordinate:

• ricevendo un puntatore al nodo da rimuovere

#+begin-example ListDelete(L,x): if x.prev != nil then x.prev.next = x.next else L.head = x.next if x.next != nil then x.next.prev = x.prev #+end-example \(O(1)\)

L’operazione é macchinosa perché bisogna controllare le condizioni “in testa” e “in coda”

• aggiungiamo nodo sentinella che rende piú omogenei i dati nella lista
  • Lista circolare

Si ha sempre la certezza che la lista contenga sempre almeno un elemento: #+begin-example ListDelete(L,x): x.prev.next = x.next x.next.prev = x.prev #+end-example \(O(1)\) comunque tempo costante minore che senza sentinella Ma il codice diventa piú semplice e leggibile

Search

In Liste doppiamente concatenate e non ordinate: #+begin-example ListSearch(L,k): x = L.head while x != nil and x.key != k do x = x.next return x #+end-example \(O(N)\)

Con sentinella: #+begin-example ListSearch(L,x): x = L.sen.next while x != L.sen and x.key != k do x = x.next return x #+end-example \(O(N)\)

Hashing

Tavole a indirizzamente diretto

\(U\) universo delle chiavi, tutte le chiavi possibili

• interi positivi tra 0 e m-1

L’insieme viene rappresentato con un array \(T\) con dimensione \(m\)

• quindi si ha indirizzamento diretto

L’insieme delle chiavi \(S\) é sottoinsieme di \(U\)

• ogni posizione di T contiene un puntatore ai dati con la chiave associata

#+begin-example TableInsert(T,x): T[x.key] = x TableDelete(T,x): T[x.key] = nil TableSearch(T,k): return T[k] #+end-example Tutte le operazioni hanno complessita temporale \(O(1)\)

Sembra molto efficiente temporalmente Non lo é sempre in termini di spazio

• se l’universo é molto grande occuperó molto spazio dovendo avere un puntatore per ognuna delle chiavi dell’universo

Tavole di hash

Possiamo utilizzare una tabella \(T\) di dimensione \(m\) molto piú piccola di \(|U|\)

• allora la posizione della chiave \(k\) é determinata utilizzando una funzione di hash in quanto non c’é piú corrispondenza diretta tra chiave e indice

Quindi:

• l’indirizzamento non é piú diretto
• la posizione di \(k\) é \(h(k)\)
• 2 chiavi possono corrispondere alla stessa posizione di \(T\)
  • una buona funzione hash riduce al minimo il numero di collisioni, cercando di distribuire in maniera casuale le coppie \(k\) e posizione

hash perfetto

• funzione che non crea mai collisione, cioé una funzione iniettiva:
  • \(k_1 \neq k_2 \implies h(k_1) \neq h(k_2)\)

Tavole hash con concatenamento

Cercano di risolvere le collisioni:

• usiamo liste per gestirle
  • allora se c’é collisione l’elemento é inserito in testa alla lista puntata dal puntatore nella posizione della array T

Il calcolo del hash ha tempo costante \(O(1)\)

#+begin-example HashInsert(T,x): L = T[h(x.key)] ListInsert(L,x) #+end-example \(O(1)\)

#+begin-example HashDelete(T,x): L = T[h(x.key)] ListDelete(L,x) #+end-example \(O(1)\) perché la lista é doppiamente concatenata

• di un elemento giá individuato

#+begin-example HashSearch(T,k): L = T[h(k)] return ListSearch(L,k) #+end-example La ricerca di un elemento richiede un tempo proporzionale alla lunghezza hella lista T[h(k)] Definiamo:

• \(m\) numero di celle in \(T\)
• \(N\) numero di elementi memorizzati
• \(\alpha = N / m\) fattore di carico
  • lunghezza media delle liste contenute nella tabella hash

caso peggiore:

• inserimenti con la stessa hash
• tutte le chiavi sono associate con la stessa cella di T
• ricerca \(O(N)\)

caso migliore:

• quando la lista T[h(k)] é vuota o contiene un solo elemento
• ricerca \(O(1)\)

caso medio:

• dipende dalla funzione hash
  • assumiamo \(O(1)\)
  • gode della proprietá di uniformitá semplice
    • uniformitá semplice
      • distribuisce in modo uniforme le chiavi fra le celle
        • ogni cella ha la stessa probabilitá di essere destinazione di una chiave casuale
• ricerca di un elemento non presente
  • individuare la lista é \(\Theta(1)\)
  • ogni lista ha la stessa probabilitá di essere associata con la chiave
  • percorrere la lista costa in media \(\Theta(\alpha)\)
  • infine il tempo richiesto é \(\Theta(1+\alpha)\)
    • \(\alpha\) non é costante!
• ricerca di un elemento che c’é
  • dipende da dove l’elemento si colloca nella lista
  • il tempo di individuare la lista é \(\Theta(1)\)
  • assumiamo che la ricerca riguardi l’i-esimo elemento inserito
    • quanti di questi finiscono nella lista di \(x_i\)?
    • ogni elemento viene inserito nella lista di \(x_i\) con probabilitá \(\frac{1}{m}\)
    • in media \(\frac{N-i}{m}\) elementi precedono \(x_i\) nella lista di \(x_i\)
  • il tempo di ricerca di \(x_i\) é proporzionale a \(1+\frac{N-i}{m}\)
  • generalizzando alla ricerca di un elemento a caso
    • \(\frac{1}{N} \sum_{i=1}^{N}(1+\frac{N-i}{m})\)
    • \(1+ \frac{\alpha}{2} - \frac{\alpha}{2N}\)
  • in totale:
    • \(\Theta(1) + \Theta(1+ \frac{\alpha}{2} - \frac{\alpha}{2N}) = \Theta(1+\alpha)\)

Si conclude che se il numero di celle in T é proporzionale a N allora \(N = O(m)\) e quindi \(\alpha = O(1)\) e la ricerca richiede tempo \(O(1)\)

Funzioni hash

Solitamente la distribuzione secondo la quale si estraggono le chiavi non é nota

• non si puó creare una funzione hash perfetta

In un Computer le chiavi sono interpretate come sequenze di bit

• si cerca di utilizzare ogni bit della chiave
• una buona funzione hash sceglie posizioni in modo tale da eliminare eventuale regalaritá nei dati

• Metodo della divisione

  Veloce ma dipende da m

  • m potenza di 2 é una buona scelta solo se si ha la certezza che gli ultimi bit hanno distribuzione uniforme

• Metodo della moltiplicazione

  m non é critico, solitamente si sceglie una potenza di 2 A dipende dai dati

  • una scelta ragionevole empiricamente é \((\sqrt{5} - 1) / 2\)

Indirizzamente aperto

Tutti gli elementi sono memorizzati nella tavola T

• l’elemento con chiave k viene inserito nella posizione h(k) se é libera
• se non é libera allora si cerca una posizione libera secondo uno schema di ispezione

Possono avvenire collisioni anche tra elementi con chiavi diverse In generale si definisce una funzione hash estesa con l’ordine di ispezione

• \(h: U \times \{0,1,2,…,m-1\} \to \{0,1,2,…,m-1\}\)

ispezione lineare

• crea file di celle occupate, ovvero addensamento primario

ispezione quadratica

• \(h(k,i) = (h^{'}(k) + c_1i + c_2i^2) \mod m\)
  • l’ordine con cui vengono esaminate le celle dipende solo dal hash della chiave k, addensamento secondario

Per risolvere questo addensamento si introduce il doppio hashing

• \(h(k,i) = (h_1(k) + ih_2(k)) \mod m\)
  • permette una uguale probabilitá per ogni sequenza di ispezione

• Insert

  #+begin-example HashInsert(T,x): for i=0 to i < m do j = h(x.key,i) if T[j] == nil then T[j] = x return j return nil #+end-example

• Search

  #+begin-example HashSearch(T,k): for i=0 to i < m do j = h(x.key,i) if T[j] = nil then return nil if T[j].key = k then return T[j] return nil #+end-example

  caso ottimale

  • posizione di una chiave scelta a caso ha distribuzione uniforme
  • qualunque sequenza di ispezione ha la stessa probabilitá
  • Elemento Assente
    • \(X\) numero di celle esaminate durante una ricerca senza successo
    • \(X\) é una variabile aleatoria
      • almeno 1:
        • \(P(X\ge 1)=1\)
      • se la prima cella é occupata dovremo esaminare 2 celle:
        • \(P(X\ge 2)= \frac{N}{m}\)
      • se la seconda cella é occupata dovremo esaminare 3 celle:
        • \(P(X\ge 3)= \frac{N}{m}\frac{N-1}{m-1}\)
      • \(P(X\ge i) \le \alpha^{i-1}}\)
      • \(E = \sum_{i=1}^{\infty}(X \ge i) \le \sum_{i=1}^{\infty} \alpha^{i-1}=\frac{1}{1-\alpha}\)
  • Elemento Presente
    • sicuramente meno celle da esaminare che nel caso dell’elemento assente

• Delete

  Inserire nil creerebbe buchi nella tabella

  • si potrebbe marcare le con costanti deleted

  Di solito l’indirizzamento aperto si usa quando non c’é necessitá di cancellazione di elementi

Pile

Inserisce chiavi in cima, rimuove le chiavi dalla cima Come ADT:

• collezione di dati
  • elementi qualunque di tipo T
• operazioni
  • void Push(Stack S, T t)
  • T Pop(Stack S)
  • T Top(Stack S)
  • bool Empty(Stack S)
  • int Size(Stack S)

applicazioni

• chiamate ricorsive di funzioni
• visita in profonditá di grafi
• valutazione di un’espressione un notazione postfissa

assiomi

• Size(S), Empty(S), Push(S,t)
  • sempre definiti
• Pop(S), Top(S)
  • sono definite iff Empty(S) é false
• Empty(S)
  • true iff Size(S) é 0
• Push(S,t); Pop(S)
  • restituisce t e non modifica S
• Push(S,t); Top(S)
  • restituisce t
• Push(S,t)
  • incremento Size(S) di uno
• Pop(S)
  • decrementa Size(S) di uno

implementazione con array

statico di M celle

• assioma ulteriore
  • Push(S,t)
    • iff Size(S) < M

meccanismo LIFO

Complessitá

• Temporale \(O(1)\)
• Spaziale \(O(M)\)

Push(S,t)
  if S.N != S.M then
    S.N = S.N + 1
    S[N] = t
  else
    error overflow

Size(S)
  return S.N

Empty(S)
  if S.N == 0 then
    return true
  else
    return false

Top(S)
  if S.N == 0 then
    error underflow
  else
    return S[S.N]

Pop(S)
  if S.N == 0 then
    error underflow
  else
    S.N = S.N - 1
    return S[S.N+1]

implementazione con lista

Conviene una lista semplice con sentinella Complessitá

• Temporale \(O(1)\)
• Spaziale \(O(N)\)
  • ma con overhead dovuto ai puntatori
  • non abbiamo un limite al massimo degli elementi

Push(S,t)
  S.N = S.N + 1
  t.next = S.sen.next
  S.sen.next = t

Size(S)
  return S.N

Empty(S)
  if S.N == 0 then
    return true
  else
    return false

Top(S)
  if S.N == 0 then
    error underflow
  else
    return S.sen.next

Pop(S)
  if S.N == 0 then
    error underflow
  else
    S.N = S.N - 1
    t = S.sen.next
    S.sen.next = S.sen.next.next
    return t

Code

• collezione di dati

  • elementi qualunque di tipo T

• operazioni

  • void Enqueue(Queue Q, T t)
  • T Dequeue (Queue Q)
  • T Front(Queue Q)

• Utilizzi

  • buffer
  • visita in ampiezza di grafi
  • simulazione di eventi complessi

assiomi

• Size Empty Enqueue
  • sempre definiti
• dequeue front
  • definiti iff Empty é false
• empty size e front
  • non modificano la coda
• empty
  • true iff Size é 0
• size; enqueue(Q,t)
  • N, dopo N esecuzioni di Dequeue(Q) abbiamo Front(Q) = t
• Front(Q) = t ==> Dequeue(Q) = t
• Enqueue(Q,t) incrementa Size(Q) di 1
• Dequeue(Q) decrementa Size(Q) di 1

implementazione con array

statico si tengono elementi nelle ultime posizioni

• altrimenti sarebbe necessario spostare tutti gli elementi

si usa l’array un maniera circolare

• si utilizzano riferimenti tail e head per tener conto delle posizioni dell’array
  • Q.head indica dove estrarre
  • Q.tail indica dove inserire
    • se head == tail allora la coda é vuota

Complessitá

• Temporale \(O(1)\)
• Spaziale \(O(M)\)

Size(Q)
  if Q.tail >= Q.head then
    return Q.tail - Q.head
  else
    return Q.M - (Q.head - Q.tail)

Empty(Q)
  if Q.tail == Q.head then
    return true
  else
    return false

NextCell(Q,c)
  if c != Q.M then
    return c+1
  else
    return 1

Enqueue(Q,t)
  if Q.tail == Q.head-1 then
    error overflow
  else
    Q[Q.tail] = t
    Q.tail = NextCell(Q,Q.tail)

Front(Q)
  if Q.tail == Q.head then
    error underflow
  else
    return Q[Q.head]

Dequeue(Q)
  if Size(Q) == 0 then
    error underflow
  else
    t = Q[Q.head]
    Q.head = NextCell(Q,Q.head)
    return t

implementazione con lista

inserimenti in testa, estrazioni in coda

• lista semplice con puntatore all’ultimo elemento della coda

Q.head punta l’elemento da estrarre Q.tail punta l’ultimo elemento inserito Q.head == nil <==> la coda é vuota Q.N tiene conto del numero di elementi

Complessitá

• Temporale \(O(1)\)
• Spaziale \(O(N)\)
  • con overhead dei puntatori
  • non abbiamo il vincolo del massimo degli elementi

Enqueue(Q,t)
  if Q.N == 0 then
    Q.head = t
    Q.tail = t
  else
    Q.tail.next = t
    Q.tail = t
  Q.N = Q.N +1

Size(Q)
  return Q.N

Empty(Q)
  return Q.N == 0

Front(Q)
  if Empty(Q) then
    error underflow
  else
   return Q.head

Dequeue(Q)
  if Empty(Q) then
    error underflow
  else
    t = Q.head
    Q.head = Q.head.next
    Q.N = Q.N -1
    return t

Alberi

Strutture gerarchiche: \(a \in A \land T_1 \in T(A) \land T_2 \in T(A) \land … \land T_k \in T(A)\implies \{a,T_1,T_2,…,T_k\} \in T(A)\)

• k >= 0

• A insieme di etichette

• T(A) insieme di alberi su A

• a radice

• Un albero é un grafo connesso aciclico

  • una radice é un nodo privilegiato
  • una foglia é un nodo da cui non esce alcun arco
  • se un nodo non é foglia é interno
  • il grado di un albero é il massimo numero di figli di un nodo
  • un insieme di alberi é una foresta

• Ma un grafo non é detto sia un albero

Cammino

• sequenza di archi cascuno incidente sul vertice di quello successivo
• un cammino da una radice ad una foglia si dice ramo

Livelli

• insiemi di vertici equidistandi dalla radice
• altezza
  • massima distanza dalla radice di un livello non vuoto (n. livelli -1)

Le operazioni di Cardinalitá e Altezza

• hanno complessitá temporale simile a quella di visita
  • \(O(n)\)

Binary Trees

Alberi binari posizionali \(BT(A)\) definito induttivamente

• albero vuoto
• sottoalberi sinistro destro

Rappresentato all’interno di un Computer:

• key (etichetta)
  • left (puntatore)
  • right (puntatore)

BTCard(Tree T)
  if(T == nil)
    return 0
  else
    return 1 + BTCard(T.left) + BTCard(T.right)
  end if

BTHeight(Tree T)
  if(T == nil)
    return -1
  else
    l = BTHeight(T.left)
    r = BTHeight(T.right)
    return 1 + max(l,r)
  end if

La complessitá sará uguale a quella di una visita (completa) di un albero

K-ary Trees

per ogni nodo

• key
• lista di puntatori

É possibile codificare ogni albero k-ario con un albero binario

• ogni nodo punta al primo figlio e al primo fratello
• key
  • child
  • sibling
• si perde la connessione diretta tra genitori e figli non primi

k-TCard(Tree T)
  if(T == nil)
    return 0
  else
    card = 1
    C = T.child
    while C != nil do
      card = card + k-TCard(C)
      C = C.sibling
    end while
    return card
  end if

Ma la rappresentazione binaria permetterebbe anche l’algoritmo BTCard()

k-THeight(Tree T)
  if(T.child == nil)
    return 0
  else
    h = 0
    C = T.child
    while C != nil do
      h = max(h,k_THeight(C))
      C = C.sibling
    return h+1
  end if

In questo caso non é possbile utilizzare l’algoritmo per alberi binari

Visite

Stessa complessitá degli algoritmi di Cardinalitá e Altezza per alberi

• In profonditá DFS

  DFS con preordine sinistro

  Tree-DFS(k-Tree T)
    visit T.key
    C = T.child
    while C != nil do
      Tree-DFS(C)
      C = S.sibling
    end while
  

  DFS iterativo con preordine destro utilizzando uno Stack

  • l’ordine di visita é l’ordine di rimozione dallo Stack

  Tree-DFS-Stack(k-Tree T)
    S = empty stack
    Push(S,T)
    while S != empty stack do
      T' = Pop(S)
      visits T'.key
      for all C child of T' do
        Push(S,C)
      end for
    end while
  

• In ampiezza BFS

  Non operabile con una ricorsione Iterativo utilizzando una coda

  • l’ordine di visita é l’ordine di rimozione dalla Coda

  Tree-BFS(k-Tree T)
    Q = empty queue
    Enqueue(Q,T)
    while Q != empty queue do
      T' = Dequeue(Q)
      visits T'.key
      for all C child of T' do
        Enqueue(Q,C)
      end for
    end while
  

• Complessitá

  • in base alla cardinalitá n dell’albero
  • il numero di cicli dipendono molto dalla struttura dell’albero
    • possiamo contare il numero di operazioni Push/Pop e Enqueue/Dequeue
    • ogni nodo dell’albero viene inserito ed estratto esattamente una volta
      • \(O(2n) = O(n)\)
        • sono ottimi in quanto per visitare un albero bisogna visitare almeno \(n\) volte l’albero

Alberi di Ricerca

Definizione induttiva

• non basta fare verifiche localmente

Con una radice \(a\) con agganciati due BRT \(l\) e \(r\)

• tutti gli elementi di \(l\) sono minori di \(a\)
• tutti gli elementi di \(r\) sono maggiori di \(a\)

Questa regola vale per tutto l’albero

\(n\) numero dei nodi \(h\) numero di archi che compongono il ramo piú lungo

i BRT possono diventare anche molto sbilanciati

• dipende dall’ordine in cui vengono inseriti gli elementi

Ric-Search(x, T)
  if x < T.key then
    Search(x,T.left)
  else if x > T.key then
    Search(x,T.right)
  else
    return T
  end if

Complessitá \(O(h)\) con \(h\) altezza di \(T\) nel caso peggiore

It-Search(x, T)
  Tree S = T
  while S != nil and S.key != x do
    if S.key < x then
      S = S.right
    else
      S = S.left
    end if
    return S

Stampa in Ordine

• pre: T binario di ricerca
• post: stampate le chiavi di T in ordine

Print-Inorder(T)
  if T != nil
    Print-Inorder(T.left)
    print(T.key)
    Print-Inorder(T.right)
  end if

Minimo

Tree-Min(T)
  if T.left != nil then
    return Tree-Min(T.left)
  end if
  return T

Massimo

Tree-Max(T)
  if T.right != nil then
    return Tree-Max(T.right)
  end if
  return T

Successore

• pre: N nodo di un albere bin. di ricerca
• post: il successore di N se esiste, nil altrimenti

Tree-Successor(N)
  if N.right == nil then
    Tree P = N
    while P.right == N and P != nil do
      N = P
      P = N.parent
    end while
    return P
  else
    return Tree-Min(N.right)
  end if

Un inserimento avviene a livello delle foglie sostituendo un sottoalbero vuoto (nil) in modo che l’albero rimanga albero di ricerca

Tree-Insert(N,T)
  P = nil
  S = T
  while S != nil
    P = S
    if N.key = S.key then
      return
    else
      if N.key < S.key then
        S = S.left
      else
        S = S.right
      end if
    end if
  end while
  N.parent = P
  if P == nil then
    T = N
  else
    if N.key < P.key then
      P.left = N
    else
      P.right = N
    end if
  end if

Cancellazione Nel caso particolare che N abbia un solo figlio

1-Delete(N,T)
  if N == T then
    if N.left != nil and N.right == nil then
      T = N.left
    else
      T = N.right
    end if
    N.parent = nil
  else
    P = N.parent
    if N == P.left then
      if N.left != nil and N.right == nil then
        P.left = N.left
        N.left.parent = P
      else
        P.left = N.right
        N.right.parent = P
      end if
    else
      if N.left != nil and N.right == nil then
        P.right = N.left
        N.left.parent = P
      else
        P.right = N.right
        N.right.parent = P
      end if
    end if
  end if

Quindi risolvendo il caso piú generale:

Tree-Delete(Z,T)
  if Z.left == nil and Z.right == nil then
    if Z == T then
      T = nil
    else
      if Z.parent.left = Z then
        Z.parent.left = nil
      else
        Z.parent.right = nil
  else
    if Z.left == nil or Z.right == nil then
      1-Delete(Z,T)
    else
      Y = Tree-Min(Z.right)
      Z.key = Y.key
      Tree-Delete(Y,T)

Salvataggio in lista

• inserire gli elementi di un BRT in ordine in una lista
• stessa tecnica per Print-Tree
• O(n) best case sbilanciato a destra
• O(n^2) worst case sbilanciato a sinistra

ToList-InOrder(T)
  if T == nil then
    return nil
  else
    L = ToList-InOrder(T.left)
    R = ToList-InOrder(T.right)
    R = ListInsert(T.key,R)
    return Append(L,R)

Visitando i nodo in ordine decrescente di etichette si evita l’utilizzo di Append

• O(n)

ToList-InOrder(T,L)
if T == nil then
  return L
else
  L = ToList-InOrder(T.right,L)
  L = ListInsert(T.key,L)
  return ToList-InOrder(T.left,L)

Copia isomorfo di un albero

• inserimenti successivi di una lista dei nodi visitati in preordine di T

• Red-Black

  Alberi binari di ricerca bilanciati Questo é utile in alberi in cui le operazioni in cui l’altezza conta sono usate spesso

  • in un albero sbilanciato
    • \(h = n-1\)
  • un albero bilanciato
    • \(h\) proporzionale al logaritmo di \(n\)
    • \(n=2^h\)

  Senza meccanismi particolari la forma dell’albero dipende solamente dall’ordine dell’inserimento

  \(R-N\) é un BRT aumentato, i cui vertici sono colorati di rosso o nero:

  • nero: la radice e tutte le foglie (nil) sono nere
  • rosso: se un nodo é rosso tutti i suoi figli sono neri
    • nodi adiacenti non possono essere entrambi rossi
  • cammino: per ogni nodo x tutti i cammini da x ad una foglia hanno lo stesso numero di nodi neri

  \(bh(x) =\) altezza nera di x

  • numero di nodi neri su un ramo a x ad una foglia(nil) (x escluso)

  Proposizione

  • l’altezza massima di un albero R-N con n nodi é \(2 \log_2(n+1)\)
    • limite massimo di \(h\)

  Ricerca \(O(\log n)\) Inserimento \(O(\log n)\) Cancellazione \(O(\log n)\)

  Queste peró devono mantenere l’albero bilanciato

  • Rotazione

    • dopo una rotazione l’albero rimane di ricerca
    • se non rispettava le regole R-N dopo le rispetta

    Left-Rotate(T,x)
      y = x.right
      x.right = y.left
      y.parent = x.parent
      if x.parent == nil then
        T = y
      else
        if x.parent.left == x then
          x.parent.left = y
        else
          x.parent.right = y
      if x.right != nil then
        x.right.parent = x
      y.left = x
      x.parent = y
    

  • Inserimento

    1. x(R) come in albero binario
       1. se x radice allora colorato B
    2. …
       1. Caso 0
          • p(B)
            • altezza B di p non cambia
       2. Caso 1
          • u(R), p(R) altrimenti Caso 0
            • violata la regola R
              • invertiamo colori di p,u con quello di g
            • dopo le modifiche le regole localmente sono rispettate
              • p di g (B) regole rispettate
              • p di g (R) regola del R violata
              • g radice basta colorarla di B
          • puó causare problemi a livelli superiori
            • u(R) si ricolora come prima
              • invertiamo colori di p,u con quello di g come Caso 1
            • u(N) e x figlio sinistro
              • rotazione g verso destra come Caso 2
            • u(N) e x figlio destro
              • 2 rotazioni come Caso 3
       3. Caso 2
          • p(R) u(B) ed é nil
            • rotazione verso destra di g
            • regola R violata
            • g(B) diventa R
            • p(R) deventa B
            • localmente le regole vengono rispettate
            • l’altezza B del padre di p non cambia
       4. Caso 3
          • u(B) ed é nil e x figlio destro
          • rotazione a sinistra di p
          • rotazione a destra di g
          • ricondotto al Caso 2

    x é il nodo che puó creare problemi

    RB-Insert-Fixup(T,x)
      while x.p.color = red do
        if x.p == x.p.p.left then
          u = x.p.p.right
          if u.color = red then     // caso 1?
            x.p.color = black
            u.color = black
            x.p.p.color = red
            x = x.p.p
          else                      // caso 2 e 3
            if x == x.p.right then  // caso 3?
              x = x.p
              Left-Rotate(T,x)
            x.p.color = black
            x.p.p.color = red
            Right-Rotate(T,x.p.p)
        else
          // corpo del if esterno con left e right scambiati, rotazioni scambiate
      T.root.color = black
    

  • Cancellazione

    1. cancellazione come in un albero di ricerca ordinario
    2. ripristino delle regole per ricolorazioni/rotazioni
       • x mantiene il suo colore
       • y prende il colore di z
       • lostcolor memorizza il nodo effettivamente perso: nel caso A,B z, nel caso C,D y
         • se il nodo rimosso é B allora viene violata la regola dei cammini
       • Caso -1
         • lostcolor = R
         • non si fa nulla
       • Caso 0
         • lostcolor = B, x é rosso
         • violate regola R, regola dei cammini
           • x puó essere radice e R
         • si colora x di B

Grafi

\(G = (V,E)\)

• vertici,archi

Un grafo puó essere orientato o meno se la relazione é asimmetrica o simmetrica Un grafo é un multigrafo se ci sono piú archi tra le stesse coppie

Un vertice \(x\) é adiacente a \(y\) se \((y,x)\in E\)

Il grado entrante di un vertice é il numero di archi entranti, viceversa per il grado uscente Il grado é la somma di g entrante e g uscente

peso di un arco in un grafo pesato é diverso da 1 il grado pesato somma i pesi degli archi

Un cammino in un grafo é una sequenza di vertici tale che \((v_i,v_{i+1})\in E\) per \(1<i<n\) cammino semplice se tutti i vertici sono distinti eccetto al piú il primo e l’ultimo vertice della sequenza Se esiste un cammino \(p\) tra i vertici \(x\) e \(y\), si dice che \(y\) é raggiungibile da \(x\) e si scrive \(x \rightarrow y\)

• in un grafo orientato la raggiungibilitá non é simmetrica

Un grafo non orientato é connesso se esiste un cammino da ogni vertice ad ogni altro vertice Un grafo orientato é

• fortemente connesso se esiste un cammino da ogni vertice ad ogni altro vertice
• debolmente connesso se il grafo ottenuto ignorando la direzione degli archi é connesso

In ciclo é un cammino che parte da un certo vertice e ci torna, dove ci sono almeno 2 archi

• se il grafo non é orientato allora é un ciclo solo se non si utilizzano due volte lo stesso arco

un grafo aciclico é detto Directed Acyclic Graph se orientato

Un grafo non é completo se ci sono vertici da cui non partono archi

• se completo il numero di archi é \(n-1\)

Un albero libero (senza radice definita) é un grafo non orientato, connesso, aciclico Foresta é un grafo non orientato, aciclico ma non necessariamente connesso

Rappresentazioni

In un computer possiamo utilzzare diverse tecniche

Matrice di adiacenza

• troppi zeri
• simmetrica per grafi non orientati

Lista di adiacenza

• ogni nodo ha associata una lista di nodi adiacenti
• doppio del numero di archi nelle liste se il grafo non é orientato

Semplicemente estendibile per i grafi pesati

Visita

3 sottoinsiemi

• Bianchi, nodi non ancora scoperti
• Grigi, nodi scoperti di cui gli adiacenti non sono ancora tutti scoperti
  • la frangia da cui continuare la visita
• Neri, nodi scoperti cui adiacenti sono stati giá scoperti

Inizializza(G)
  for \forall u \in V do
    u.color = bianco
    u.predecessor = nil

Visita(G,s)                             // s nodo da cui partire
  s.color = grigio
  while \exists nodo grigio do
    u = nodo grigio
    if \exists v bianco \in adj[u] then // adiacente bianco?
      v.color = grigio
    else                                // u non ha adiacenti bianchi
      u.color = nero

• proprietá
  • colore puó solo passare da B a G a N
• invarianti
  • se \((u,v) \in E\) e \(u\) é N allora \(v\) é G o N
  • tutti i vertici G o N sono raggiungibile da s
  • qualunque cammino da s ad un nodo B deve contenere almeno un vertice G
• teorema
  • un vertice \(v\) é N \(\iff\) é raggiungibile da \(s\)

Visita(G,s)
  s.color = grigio
  while \exists nodo grigio do
    u = nodo grigio
    if \exists v bianco \in adj[u] then
      v.color = grigio
      v.predecessor = u
       else
      u.color = nero

• proprietá
  • al termine di Visita(G,s), l’unico vertice nero con predecessore nil é s
• teorema
  • il sottografo dei predecessori é un albero
    • un albero di scoperta

Questo Algoritmo visita solo il componente di cui il nodo iniziale (s) fa parte

• il Grafo puó non essere connesso

Visita intera di un grafo non connesso:

Visita-Tutti-Vert(G)
  Inizializza(G)
  for \forall u \in V do
    if u.color == bianco then
      Visita(G,u)

Il sottografo di predecessori diventa una foresta se il grafo contiene piú componenti

• foresta di scoperta

• Versione piú concreta

  • operazioni, D insiemi dei nodi Grigi
    • Make-Empty
      • crea una nuova struttura
    • First(D)
      • restituisce il primo elemento senza modificare D
    • Add(D,x)
      • aggiunge x a D
      • se aggiunge x come primo el -> stack
      • se aggiunge x come ultimo el -> queue
    • Remove-First(D)
    • Not-Empty(D)

  Visita(G,s)
    D = Make-Empty
    s.color = G
    Add(D,s)
    while Not-Empty(D) do
      u = First(D)
      if \exists v B \in adj[u] then   // come implementarlo?
        v.color = G
        v.p = u
        Add(D,v)
      else
        u.color = N
        Remove-First(D)
  

  Complessitá \(O(|V|)\) per le operazioni su D e \(O(|E|)\) per la ricerca dei nodi B

  • tempo totale \(O(|V|+|E|)\)

  D coda

  • visita in ampiezza (breadth first search - BFS)
  • la costruzione del livello n+1 non comincia prima di concludere la costruzione del livello n

  In una coda possiamo modificare l’Algoritmo cosí:

  Visita(G,s)
    D = Make-Empty
    s.color = G
    Add(D,s)
    while Not-Empty(D) do
      u = First(D)
      for \forall v: v.color == B \in adj[u] do // in quanto il primo el non cambia
                                                // finché ci sono adiacenti B
        v.color = G
        v.p = u
        Add(D,v)
      u.color = N
      Remove-First(D)
  

• Versione ulteriore BFS

  Breadth First Search due campi per ogni el nella lista di adiacenti

  • vtx é il vertice
  • next é il prossimo

  Visita(G,s)
    D = Make-Empty
    s.color = G
    Add(D,s)
    while Not-Empty(D) do
      u = First(D)
      ptr = adj[u]
      while ptr != nil do
        v = ptr.vtx
        if v.color == B then
          v.color = G
          v.p = u
          Add(D,v)
        ptr = ptr.next
      u.color = N
      Remove-First(D)
  

  Con calcolo di Livello d:

  Inizializza(G)
    for  \forall u \in V do
      u.color = B
      u.p = nil
      u.d = \infty
  
  Visita(G,s)
    D = Make-Empty
    s.color = G
    s.d = 0
    Add(D,s)
    while Not-Empty(D) do
      u = First(D)
      ptr = adj[u]
      while ptr != nil do
        v = ptr.vtx
        if v.color == B then
          v.color = G
          v.p = u
          v.d = u.d + 1
          Add(D,v)
        ptr = ptr.next
      u.color = N
      Remove-First(D)
  

  La forma dell’albero dipende dall’ordine un cui si trovano i nodi nelle liste di adiacenza

  • teorema al termine della visita BFS
    • \(\forall v \in V,v.d = \delta(s,v)\)
  • proprietá
    • il cammino da s a v nell’albero BFS é un cammino minimo
    • il livello di un nodo nell’albero ottenuto con la visita BFS é indipendente dal ordine in cui sono memorizzati i vertice nelle liste di adiacenza

• Versione ulteriore DFS

  Depth First Search Ordine di scoperta con un contatore

  • inc quando un nodo cambia colore
  • ogni nodo é marcato 2 volte (B -> G, G -> N) su 2 attributi
    1. inizio visita
    2. fine visita

  Inizializza(G)
    for \forall u \in V do
      u.color = B
      u.p = nil
      u.ptr = adj[u]
  
  Visita(G,s)
    D = Make-Empty
    s.color = G
    Add(D,s)
    while Not-Empty(D) do
      while First(D).ptr != nil do
        v = First(D).ptr.vtx
        First(D).ptr = First(D).ptr.next
        if v.color == B then
          v.color = G
          v.p = First(D)
          Add(D,v)
      First(D).color = N
      Remove-First(D)
  

  La struttura di attivazione rivela che un vertice non viene disattivato finché non sono stati attivati e disattivati tutti i suoi discendenti

  • stesso ordine in cui si percorre un albero di ricorsione

  Visita(G,s)
    s.color = G
    while \exists v: v == B \in adj[s] do
      v.p = s
      Visita(G,v)
    s.color = N
  

  C’é corrispondenza fra lo stack della versione iterativa e lo stack delle attivazione della procedura ricorsiva

  Contatore time per ricordare l’ordine della attivazioni/disattivazione

  • .d
  • .f

  Inizializza(G)
    for \forall u \in V do
      u.color = B
      u.p = nil
      u.ptr = adj[u]
      u.d = \infty
      u.f = \infty
    time = 1
  
  Visita(G,s)
    s.color = G
    s.d = time
    time = time + 1
    while \exists v: v == B \in adj[s] do
      v.p = s
      Visita(G,v)
    s.f = time
    time = time + 1
    s.color = N
  

  • Proprietá

    • Teorema delle parestesi
      • ogni visita DFS in un grafo, \(\forall (u,v) \in G\) 1 e 1 sola di queste condizioni é soddisfatta:
        1. u.d < v.d < v.f < u.f e u é antenato di v in un albero della foresta DFS
           • nel G esiste un cammino do u a v
        2. v.d < u.d < u.f < v.f e u é discendente di v in un albero della foresta DFS
           • nel G esiste un cammino da v a u
        3. u.d < u.f < v.d < v.f o v.d < v.f < u.d < u.f e non esiste relazione antenato-discendente tra u e v nella foresta DFS
           • u e v fanno parte di 2 alberi distinti, nel G non esiste cammino da uno all’altro
    • classificazione degli archi del grafo durante DFS
      • arco dell’albero
        • inserito nella foresta DFS
      • arco all’indietro
        • nodo - antenato
      • arco in avanti
        • nodo - discendente
      • arco di attraversamento
        • nodi - nodo non in relazione antenato-discendente,
          • due alberi distinti della foresta
          • due rami distinti dello stesso albero

    La classificazione é fatta quando si esamina v nella lista di adiaceti adj[u]

    • v.color:
      • B, (u,v) arco della foresta
      • G, u discendente di v (u,v) arco all’indietro
      • N, visita v giá terminata, (u,v) é un arco
        • in avanti se v é discendente di u
          • u.d < v.d \(\implies\) u.d < v.d < v.f < u.f
        • di attraversamento altrimenti
          • v.d < u.d \(\implies\) v.d < v.f < u.d < u.f
    • teoremi
      • in una visita DFS di un G non orientato, ogni arco é un arco dell’albero o un arco all’indietro
      • un G, orientato o meno, é aciclico se e solo se una visita DFS non produce archi all’indietro

Cammino di scoperta

Print-Path(G,s,u)
  if u == s then
    print u
  else
    if u.predecessor == nil then
      print "Non c'é cammino da s a u"
    else
      Print-Path(G,s,u.predecessor)
      print u

Ordinamento Topologico

• Def, Proprietá

  \(\sigma : V \rightarrow \{1,…,|V|\}\) t.c. \(\sigma(u) < \sigma(v)\) se esiste un cammino da \(u\) a \(v\) in \(G\) Ció ha senso solo in grafi orientati def equivalente: un ordinamento lineare dei vertici di un grafo tale che \(\forall (u,v) \in E\), \(u\) precede \(v\) nell’ordinamento

  L’ordinamento puó esistere solo se il grafo é aciclico (DAG) Ne puó esistere piú di uno

• Algoritmo naive

  • il primo nodo deve essere senza archi entrambi, denotato \(o_1\)
  • il secondo nodo puó avere archi entranti solo da \(o_1\), denotato \(o_2\)
  • il terzo nodo puó evere archi entranti solo da \(o_1,o_2\), denotato i\(o_3\)
  • …

  Topological-Order(G)
    H = G
    o = lista vuota di vertici
    while \exists u: \not\exists v: (v,u) \in E(H) do
      o.append(u)
      H.remove(u)
    if H != vuoto
      print "grafo non aciclico"
    return o
  

• Algoritmo DFS

  In ordine di attributo fine visita decrescente

  • si parte alla radice dell’ultimo albero DFS
    • si scorrono i rami da destra a sinistra

  Topological-Sort(G)
    L = lista vuota di vertici
    Inizializza(G)
    for all u in V do
      if u.color == B then
        DFS-Topological(G,u,L)
    return L
  
  DFS-Topological(G,s,L)
    s.color = g
    s.d = time
    time = time + 1
    for all v == b && in adj[s] do
      v.p = s
      DFS-Topological(G,v,L)
    s.color = nero
    s.f = time
    time = time + 1
    L.insert(s)        // in testa
  

  Complessitá sempre uguale a quella della visita in profonditá

Componenti Fortemente Connesse

cfc

• Def, Proprietá

  2 nodi u,v sono mutualmente raggiungibili se u é raggiungibile da v e viceversa In un grafo \(G = (V,E)\) la relazione \(V \for V\) mutualmente raggiungibile é una relazione di equivalenza (riflessiva, simmetrica, transitiva) Le cfc di un grafo orientato sono le classi di equivalenza su questa relazione \(u \leftrightarrow v\) simboleggia la appartenenza alla stessa classe di equivalenza, e alla stessa cfc

• Naive

• DFS

  • lemmi
    1. se \(x \leftrightarrow y\) allora nessun cammino tra essi puó uscire dalla loro cfc
  • teoremi
    1. in una qualunque DFS di un grafo G orientato tutti i vertici di una cfc vengono collocati nello stesso albero
       • nello stesso albero di scoperta ci sono nodi di piú cfc

  Gli alberi della foresta di scoperta si possono, sempre, potare in modo da separare le cfc

  Consideriamo il grafo trasposto:

  • dall’alto al basso
  • da destra verso sinistra

  Intervalli di attivazione di due vertici

  1. x.d < y.d < y.f < x.f
  2. y.d < y.f < x.d < x.f

  In entrambi i casi x.f > y.f

  • i vertici vanno considerati in ordine decrescente di tempo di fine visita

  Algoritmo:

  1. visita \(G\) in profonditá preparando una lista dei vertici in ordine decrescente dei tempi di fine visita
  2. costruisci \(G^T\)
  3. visita \(G^T\) in profonditá considerando i vertici secondo la lista restituita dal passo 1. per quanto riguarda la scelta del nodo bianco da dove fare (ri)partire la visita

  Complessitá: \(3 * O(|V| + |E|) = O(|V|+|E|)\)

Albero Minimo Ricoprente

Minimal Spanning Tree dato un grafo \(G(V,E)\)

• connesso
• non orientato

un albero ricoprente é un sottografo che

• contiene tutti i nodi
• aciclico
• connesso

La funzione peso \(W\) é la sommatoria dei pesi degli archi L’albero minimo ricoprente é l’a.r. \(T\) con peso minimo

• \(W(T)\) minimo

Un grafo ne puó evere piú di uno equivalenti

Min-AR(G)
  A = nil
  while A non é un ar do
    trova arco (u,v) sicuro per A
    A = A \Cup (u,v)

\((u,v)\) é un arco sicuro per \(A\):

• \(A \cup (u,v)\) é un sottoinsieme degli archi di un minimo albero di copertura di \(G\)

Al termine \(T=(V,A)\) é un minimo ar

• Taglio di \(G\)
  • partizione di \(V\) in due insiemi \(X\) e \(V-X\)
  • un arco attraversa il taglio se parte da \(X\) e arriva in \(V-X\)
    • gli archi in questi casi non sono orientati, é simmetrico
  • rispetta un insieme di archi se nessun arco dell’insieme attraversa il taglio
  • un arco che attraversa un taglio é leggero se é un arco di peso minimo tra quelli che attraversano il taglio
• Teorema
  • \(G(V,E)\) non orientato, connesso, pesato
  • \(A\) sottoinsieme di \(E\) contenuti in qualche ar minimo
  • \((X,V-X\) taglio che rispetta \(A\)
  • \((u,v)\) arco leggero che attraversa \((X,V-X)\)
  • \(\implies (u,v)\) sicuro per \(A\)
    • per allargare la soluzione parziale
• Corollario
  • \(C\) componente connessa nella foresta \(G(A)=(V,A)\)
  • \((u,v)\) arco leggero che connetta \(C\) a una qualche altra componente connessa di \(G(A)\)
  • \(\implies (u,v)\) sicuro per \(A\)

Algoritmo di Kruscal

mantiene sottografo non necessariamente connesso di un MST

• inizialmente:
  • tutti i vertici e nessun arco
  • per ogni arco, in ordine non decrescente di costo
    • arco con entrambi gli estremi nella stessa componente connessa
      • scarto
    • viceversa incluso nella soluzione

L’algoritmo si ferma una volta aggiunti \(|V| - 1\) archi ad \(A\)

MST-Kruskal(G)
  A = nil
  ordina gli archi in ordine crescente di peso
  for all (u,v) nell'ordine do
    if (u,v) non crea ciclo in G(A) then
      A = A + (u,v)

Sequenza di n+m operazioni MakeSet, FindSet e Union di cui:

• n sono MakeSet
  • n nodi diventano n alberi o insiemi
• m sono Union e/o Find
  • m archi cercati e uniti se sicuri

La UnionFind esegue una tale sequenza in tempo \(O((n+m) \log n)\) nel caso peggiore

MST-Kruskal(G)
  A = empty_set
  for all v in V do
    MakeSet(v)
  ordina archi per peso crescente
  for all (u,v) in E nell'ordine do
    if Find(u) != Find(v) do
      A = A + (u,v)
      Union(u,v)

• Complessitá

  Ordinamento: \(O(|E|\log |E|)\) Operazioni sulla foresta di insiemi disgiunti: \(O((|V|+|E|) \log |V|)\) Il grafo é connesso: \(O((|V|+|E|) \log |V|) = O(|E|\log |V|)\) Totale: \(O(|E|\log |E|) = O(|E| \log |V|^2) = O(|E|2\log |V|) = O(|E|\log |V|)\)

• Correttezza

  Invariante: \(A\) é un sottoinsieme degli archi di un MST di \(G\)

  • inizializzazione: \(A = \emptyset\) OK
  • ciclo for:
    • se l’arco crea un ciclo non viene aggiunto
    • se non crea un ciclo allora per corollario l’arco é sicuro e OK

  Si dimostra per assurdo che al termine del algoritmo \((V,A)\) é connesso

Algoritmo di Prim

Mantiene un sottografo connesso \((V-Q,A)\) di un MST

• inizialmente consiste di un nodo arbitrario
  • \(Q\) contiene tutti i nodi tranne questo nodo iniziale
  • \(A\) é vuoto
• \(n-1\) volte:
  • sceglie un arco \((u,v)\) di peso minimo che collego un nodo in \(V-Q\) ad un nodo in \(Q\)
    • aggiungilo a \(A\)
    • togli da \(Q\) il vertice a cui porta l’arco

MST-Prim(G,s)
  A = emptyset
  Q = V - {s}
  while Q != emptyset
    scegli arco (u,v) con peso minimo e u in V-Q, v in Q
    A = A + (u,v)
    Q = V - {v}

Per facilitare la scelta dell’arco successivo memoriziamo per ogni nodo \(u \in Q\) l’arco piú leggero fra \(V-Q\) e \(u\)

• attributo \(\pi\) é l’estremitá dell’arco in \(V-Q\) e \(d\) il suo peso

MST-Prim(G,s)
  Q = V
  for all v in V do v.d = infty
  s.d = 0
  s.pi = nil
  while Q != emptyset do
    u = nodo con d minimo in Q (tolto da Q)
    for all v in adj[u] do
      if v in Q && W(u,v) < v.d then
        v.d = W(u,v)
        v.pi = u

• Complessitá

  \(Q\) puó essere implementata come coda di prioritá usando un heap minimo Le prioritá sono date dall’attributo \(d\) il costo dell’algoritmo di Prim é limitato da:

  • inizializzazione: \(O(|V|)\)
  • estrazioni del minimo: \(O(|V|\log |V|)\)
  • risistemazione dello heap benario dopo il decremento eventuale delle chiavi: \(O(|E|\log |V|)\)

  Complessitá: \(O((|V|+|E|)\log |V|) = O(|E|\log|V|)\)

• Correttezza

  Invarianti

  1. \(\forall t \in Q: t.\pi \neq nil \implies t.\pi \in V-Q\)
  2. \(\forall t \in Q: (t.\pi ,t)\) un arco di peso minimo tra \(t\) e un vertice di \(V-Q\)
  3. \((V-Q,\{(t.\pi ,t): t \neq s,t \in V-Q\})\) é un sottografo di un MST:
     • inizialmente vero in quanto un solo nodo
     • corpo del ciclo:
       • \(u\) vertice estratto da \(Q\)
       • per invariante 1. e 2. l’arco \((u.\pi ,u)\) é un arco leggero che unisce le componenti connesse \((V-Q,A)\) e \((\{u\}, \emptyset)\)
       • \(\implies\) arco sicuro per corollario

Cammini Minimi

dato un \(G\) orientato e pesato Definiamo distanza di un vertice \(u\) da un vertice \(v\): \(\delta(u,v)\), il peso di un cammino di peso minimo tra tutti i cammini da \(v\) a \(u\). Una tale distanza é ben definita se non contiene al suo interno archi con peso negativo. Un algoritmo per trovare cammini minimi da un dato nodo:

• input
  • G orientato e pesato
  • un nodo sorgente \(s\)
• output
  • \(\forall v \in V(G)\) l’attributo \(v.d\) indica la distanza dal vertice sorgente
  • l’attributo mantiene una approssimazione della distanza dal nodo sorgente

Si costruisce un albero radicato in \(s\) che percorre tutti i cammini minimi

• man mano che si inseriscono i vertici con il loro costo si controllano i suoi adiacenti, in quanto potrebbe esserci un cammino dal costo minore di quello precedentemente considerato passante dall’ultimo vertice aggiunto

• Algoritmo di Dijkstra

  Dijkstra(G,s)
    Q = V
    for all v in V do v.d = infty, v.p = nil
    s.d = 0
    s.p = nil
    while Q != empty do
      u = togli nodo con d minimo da Q
      for all v in adj[u] do
        if v in Q && u.d + W(u,v) < v.d then
          v.d = u.d + W(u,v)
          v.p = u
  

  • Complessitá

    Simile all’algoritmo di Prim

    • entrambi costruiscono un albero

    La complessitá di Dijkstra é uguale a quella di Prim

  • Correttezza

    • proprietá
      1. un sottocammino di un cammino minimo é minimo
    • invarianti banali
      1. \(\forall v \in V(G): v \notin Q \implies v.d\) non modificato
      2. \(\forall v \in Q: v.\pi \neq nil \implies v.\pi \notin Q\)
      3. \(\forall v \in V(G) - \{s\}: v.d \neq \infty \iff v.\pi \neq nil\)
      4. \(\forall v \in V(G) - \{s\}: v.d \neq \infty \implies v.d = v.\pi .d + W(v.\pi,v)\)
    • invariante del ciclo
      1. \(\forall v \notin Q : v.d \neq \infty \iff\) esiste un cammino da (s,v) in G
    • invariante principale del ciclo
      1. \(\forall t \notin Q: t.d = \delta(s,t)\)

Disjoint-Set Forest

Vedi progetto svolto per esercizio:

• Union-Find Set