Heap 09/09/2014

Dare la definizione di max-heap e dire se ‹23,17,14,6,13,10,1,5,7,12› è un max-heap giustificando la risposta.

Svolgimento

Un max-heap è un albero in cui gli elementi sono tutti non maggiori dell'elemento padre.

L'implementazione ad array di uno heap binario consiste nel posizionare come primo elemento la radice dell'albero (23, nell'esercizio) e poi per ogni livello l 2l elementi, in posizione 2l e 2l+1.

L'albero corrispondente all'array è quindi

               23
      17              14
  6        13      10     1
5   7    12

Dal momento che 7 > 6, questo non è un max-heap.

Hash - 12/06/2014

In una tabella Hash di m = 17 posizioni, inizialmente vuota, devono essere inserite le seguenti chiavi numeriche nell’ordine indicato:

23, 40, 15, 58, 85

Indicare per ogni chiave la posizione finale dove viene allocata in questi due casi:

a. Funzione Hash:

h(k) = k mod m

Risoluzione delle collisioni mediante concatenamento

b. La tabella è a indirizzamento aperto e la scansione è eseguita per doppio Hashing:

h(k, i) = (k mod m + i * 2k mod 5) mod m

Si devono indicare tutte le posizioni scandite nella tabella.

Svolgimento

Caso A:

  1. 23 mod 17 = 6 → 6[0] = 23
  2. 40 mod 17 = 6 → 6[1] = 40
  3. 15 mod 17 = 15 → 15[0] = 15
  4. 58 mod 17 = 7 → 7[0] = 58
  5. 85 mod 17 = 0 → 0[0] = 85

Risultato:

0: 85; 1:; 2:; 3:; 4:; 5:; 6: 23, 40; 7: 58; 8:; 9:; 10:; 11:; 12:; 13:; 14:; 15: 15; 16:;

Caso B

  1. i = 0, k = 23: (23 mod 17 + 0 * 2*23 mod 5) mod 17 = 6
  2. i = 1, k = 40: (40 mod 17 + 1 * 2*40 mod 5) mod 17 = 6: c'è una collisione, quindi si scorre fino al numero 7
  3. i = 2, k = 15: (15 mod 17 + 2 * 2*15 mod 5) mod 17 = 15
  4. i = 3, k = 58: (58 mod 17 + 3 * 2*58 mod 5) mod 17 = 10
  5. i = 4, k = 85: (85 mod 17 + 4 * 2*85 mod 5) mod 17 = 0

Risultato:

0: 85; 1:; 2:; 3:; 4:; 5:; 6: 23; 7: 40; 8:; 9:; 10: 58; 11:; 12:; 13:; 14:; 15: 15; 16:;

Hash 28/01/2015

In una tabella Hash di m = 17 posizioni, inizialmente vuota, devono essere inserite le seguenti chiavi numeriche nell’ordine indicato:
18, 36, 155, 19
La tabella è a indirizzamento aperto e la scansione è eseguita per doppio Hashing:
h(k, i) = (k mod m + i * 2k mod 5) mod m
Indicare per ogni chiave le posizioni scandite nella tabella e la posizione finale dove viene allocata.

i = 0, k = 18 → (18 mod 17 + 1 * 218 mod 5) mod 17 = (1 + 0 * 8) mod 17 = 1

i = 1, k = 36 → (36 mod 17 + 1 * 236 mod 5) mod 17 = (2 + 1 * 2) mod 17 = 4

i = 2, k = 155 → (155 mod 17 + 2 * 2155 mod 5) mod 17 = (2 + 2 * 1) mod 17 = 4: collisione

i = 3, k = 155 → (155 mod 17 + 3 * 2155 mod 5) mod 17 = (2 + 3 * 1) mod 17 = 5

i = 4, k = 19 → (19 mod 17 + 4 * 219 mod 5) mod 17 = (2 + 4 * 16) mod 17 = 15

La hash finale è la seguente (l'indicizzazione è 0 - n-1):

[_] [18] [_] [_] [36] [155] [_] [_] [_] [_] [_] [_] [_] [_] [_] [19] [_]

Funzioni efficienti (grafi) - 08/09/2014-2

Si vuole costruire una rete stradale che colleghi cinque città (A-E), minimizzando i costi complessivi di realizzazione. I costi per la costruzione di una strada tra due città sono sintetizzati nella seguente tabella (dove +∞ significa che la strada è irrealizzabile):

A B C D E
A 0 3 5 11 9
B 3 0 3 9 8
C 5 3 0 +∞ 10
D 11 9 +∞ 0 7
E 9 8 10 7 0

Si formuli il problema dato in termini di un problema di ottimizzazione su grafi, e si descriva un algoritmo per la sua soluzione discutendone correttezza e complessità. Infine, si simuli accuratamente l’algoritmo presentato per determinare una soluzione del problema.

Svolgimento

Il grafo è non orientato, poiché la matrice di adiacenza è simmetrica.

Si può utilizzare l'algoritmo di Kruskal, che è corretto, poiché è composto da

  1. un'inizializzazione con tempo O(n) che termina sicuramente, in quanto è un ciclo
  2. un ordinamento degli archi con costo O(m log(m)), che termina sicuramente, utilizzando un algoritmo di ordinamento che termina (es. mergesort o quicksort)
  3. un ciclo per ciascun arco O(m) per ciascuno dei quali è necessario verificare se i due vertici appartengono allo stesso insieme O(log(n)) ⇒ O(m log(n)), operazione che termina sicuramente
  4. l'aggiunta dell'arco e l'unione (eventuale) dei due sottoinsiemi, con costo O(log(m)), che termina sicuramente.

e che ha un costo complessivo di esecuzione O(m log(m))

  1. gli archi ordinati sono AB(3), BC(3), AC(5), DE(7), BE(8), AE(9), BD(9), CE(10), AD(11), CD(+∞)
  2. AB costituisce il primo arco aggiunto all'albero U, e A, B i primi due vertici (nota: sarebbe stato indifferente iniziare con BC, con un esito diverso ma costi uguali). Ora U = {A, B, (AB)}
  3. BC è aggiunto, in quanto C non appartiene a U. Ora U = {A, B, C, (AB), (BC)}
  4. AC non è aggiunto, in quanto sia A sia C appartengono a U
  5. DE è aggiunto - pur non essendo ancora connesso. Ora U = {A, B, C, D, E, (AB), (BC), (DE)}
  6. BE è aggiunto, perché B ed E appartengono a due set diversi. Ora U = {A, B, C, D, E, (AB), (BC), (DE), (BE)}
  7. Per brevità riportiamo in un solo passaggio AE, BD, CE, AD, CD, che non sono inclusi.

Le strade da realizzare sono quelle evidenziate in neretto:

A B C D E
A 0 3 5 11 9
B 3 0 3 9 8
C 5 3 0 +∞ 10
D 11 9 +∞ 0 7
E 9 8 10 7 0

Funzioni efficienti (grafi) - 12/09/2016

Si stabilisca quale problema risolve il seguente algoritmo, che accetta in ingresso un grafo non orientato G = (V, E):

MyAlgorithm(G)
1. A = ∅
2. ordina i vertici di G per grado crescente
3. for each u ∈ V[G] do /* vertici estratti secondo l’ordine stabilito nel passo 2 */
4.    if MyFunction(G,A,u) then
5.       A = A ∪ {u}
6. return A
MyFunction(G,A,u)
1. for each v ∈ A do
2.    if (u,v) ∈ E[G] then
3.       return FALSE
4. return TRUE

Si dimostri la correttezza dell’algoritmo, si determini la sua complessità e si simuli infine la sua esecuzione sul seguente grafo:

Svolgimento

  1. l'algoritmo restituisce l'insieme con i gradi più bassi possibile di elementi non collegati tra loro
  2. l'algoritmo è corretto, perché, essendo composto da due cicli for innestati, termina sicuramente
  3. la complessità è data da
    1. ordinamento O(n log(n))
    2. un ciclo Θ(n), che richiama un altro ciclo Θ(n), quindi il costo complessivo è Θ(n2)
    3. la ricerca dell'arco, che a seconda dell'implementazione può essere O(n) o O(log(n))
    4. la complessità totale è quindi O(n log(n)) + Θ(n2) + O(n) ⇒ O(n2)
  4. L'esecuzione:
    1. Si considera l'elemento 6: A è vuoto, quindi MyFunction restituisce true e l'elemento viene aggiunto ad A
    2. Si considera l'elemento 1: A contiene solo 6, che non è collegato a 1. L'elemento è quindi aggiunto.
    3. Si considera l'elemento 5: non è collegato ad alcun vertice in A, quindi l'elemento è aggiunto.
    4. Si considera l'elemento 2: è collegato a 1, che è presente in A, quindi l'elemento non è aggiunto.
    5. Si considera l'elemento 4: è collegato a 5 e 6, che sono presente in A, quindi l'elemento non è aggiunto.
    6. Si considera l'elemento 3: è collegato a 1 e a 5, che sono presente in A, quindi l'elemento non è aggiunto.
    7. Il risultato finale è che A contiene 1, 5, 6.

Funzioni efficienti (grafi) 27/05/2017

Il seguente algoritmo accetta in ingresso la matrice di adiacenza di un grafo non orientato e restituisce un valore Booleano (TRUE / FALSE)

MyAlgorithm( A )
1. n = rows(A) /* determina il numero di vertici del grafo */
2. let B an n x n matrix /* alloca memoria per una matrice B n x n */
3. for i = 1 to n
4.    for j = 1 to n
5.       b[i,j] = 0
6.       for k = 1 to n
7.          b[i,j] = b[i,j] + a[i,k]*a[k,j]
8. for i = 1 to n
10.   for j = i + 1 to n
11.      if a[i,j]*b[i,j] <> 0 then
12.          return FALSE
13.return TRUE

Si calcoli la complessità computazionale di MyAlgorithm e si determini la sua funzione (in quali casi restituisce TRUE? in quali casi FALSE?). (Nota: Nel determinare la complessità si ignori per comodità la complessità delle istruzioni 1 e 2).
Si simuli inoltre il suo comportamento sui seguenti due grafi, verificando che restituisca il risultato atteso:

Risposta

L'algoritmo è trattato nella lezione 10 di Pelillo, in cui si parla del risultato di un prodotto tra la matrice di adiacenza e se stessa, e dei successivi prodotti tra la matrice e il risultato precedente.

Una volta terminato la prima serie di cicli annidati, di costo O(n3), si verifica con un'altra serie di cicli annidati, di costo O(n2), se esistono archi in comune. Se esistono (confronto alla riga 11), il grafo ha almeno un ciclo di lunghezza 3 vertici.
Il costo complessivo è O(n3) + O(n2), quindi O(n3).

Il comportamento si basa su matrice di adiacenza e matrice di appoggio.

Le matrici di adiacenza sono:

1 2 3 4
1 0 1 0 0
2 1 0 1 0
3 0 1 0 1
4 0 0 1 0

e  per il secondo grafo

1 2 3 4
1 0 1 1 0
2 1 0 1 0
3 1 1 0 1
4 0 0 1 0

Una volta terminati le 64 esecuzioni (4 x 4 x 4) della riga 7, si ottengono le seguenti matrici:

1 2 3 4
1 1 0 1 0
2 0 2 0 1
3 1 0 2 0
4 0 1 0 1

Questa matrice è "complementare" a quella del primo grafo, che infatti non presenta cicli.

1 2 3 4
1 1 1 1 1
2 1 2 1 1
3 1 1 2 0
4 1 1 0 1

Questa seconda matrice ha in comune con la seconda matrice di adiacenza i tre archi ((1, 2), (2, 3), (3, 1)) che costituiscono il ciclo.

Costi di esecuzione (strutture dati) 27/05/2015

Completare la seguente tabella indicando la complessità delle operazioni che si riferiscono a un dizionario di n elementi. Per l’operazione Successore si assuma di essere sull’elemento x a cui si applica l’operazione.

Ricerca Massimo Successore Minimo Costruzione
Albero binario di ricerca O(h) O(h) O(h) O(h) O(n)
Min-Heap O(log n) O(log n) O(log n) O(log n) O(n)

Nota: in un albero binario bilanciato, h è l'altezza dell'albero, che è uguale a log(n) per n compreso tra n^(h-1)+1 e n^h

I cinque algoritmi sui grafi da sapere

Kruskal, Prim, Dijkstra, Bellman-Ford, Floyd-Warshall

Kruskal

L'amico Kruskal vuole trovare l'albero (o gli alberi) che collega i vertici tramite gli archi più leggeri possibile.

Per fare questo, divide i vertici di un grafo in tanti sottoinsiemi quanti sono i vertici, poi ordina gli archi e considera le coppie di vertici partendo dall'arco più leggero: se i vertici appartengono allo stesso insieme, ignora l'arco; altrimenti aggiunge l'arco all'albero di copertura e unisce i due sottoinsiemi.

Il risultato è un albero di copertura minimo, il tempo di esecuzione è Θ(E log E).

_(, )
1.  ← ∅
2.  ℎ  ∈ []  //per [] intendiamo l’insieme dei vertici di 
3.   _() //abbiamo creato  insiemi, ognuno dei quali contiene un vertice
4.   ℎ        // tipico degli algoritmi Greedy
5.  ℎ (, ) ∈ []  //che sono ordinati
6.    _() ≠ _() ℎ
7.      ←  ∪ {(, )}
8.     (, )
9.  

Prim

L'amico Prim vuole trovare l'albero (o gli alberi) che collega i vertici tramite gli archi più leggeri possibile.

Per fare questo, sceglie uno dei vertici e lo inserisce nell'albero, poi controlla quale tra gli archi adiacenti è il più leggero (o i più leggeri), aggiunge il vertice all'albero e gli attribuisce un peso pari all'arco. Se durante la visita un vertice è già stato visitato, ma ha un peso maggiore dell'arco corrente, si cambia l'arco connesso e si aggiorna il peso del vertice.

Il risultato è un albero di copertura minimo, il tempo di esecuzione è O(E V log V) a patto di utilizzare per l'archiviazione dell'elenco dei vertici uno heap di Fibonacci.

_(, , )
1.  ← [] //inizializziamo Q con tutti i vertici di G
2.  ℎ  ∈  
3.   [] = ∞
4. [] = 0
5. [] = 
6. ℎ  ≠ ∅ 
7.    ← _() //estrae il vertice con campo key minore
8.    ℎ  ∈ []  //per ogni vertice adiacente al vertice estratto
9.       ∈  && (, ) < [] ℎ
10.       [] ←  //u diventa il padre di v
11.       [] ← (, ) //aggiorna il valore di key e riorganizza l’heap
12.   = {(, []) |  ∈  \ {}}

Dijkstra

L'amico Dijkstra vuole raggiungere nel tempo/spazio minore un vertice partendo da un altro vertice.

Per fare questo, come l'amico Dijkstra, inizializza tutti i vertici con peso ∞ e parent = NIL, poi iniziando dal vertice sorgente imposta nei vertici adiacenti il peso degli archi. Se arriva a un vertice già esplorato, ma il peso del vertice è maggiore del vertice "nuovo padre" più l'arco che li congiunge, ne cambia il padre e aggiorna il peso del vertice (rilassamento).

Il risultato è un albero in cui ciascun vertice è collegato alla sorgente con il percorso più breve possibile. Il costo dipende dall'implementazione dell'elenco dei vertici, e segue questa tabella:

Grafo sparso Grafo denso
Array lineare O(n2) O(n2)
Heap binario O(n log n) O(n2 log n)

dove per "Grafo sparso" si intende un grafo in cui il numero di vertici e il numero di archi tende ad essere uguale E = Θ(V), mentre per "Grafo denso" si intende che E = Θ(V2).

NOTA: Dijkstra si incasina se ci sono archi con peso negativo.

__(, )
1.  ℎ  ∈ []
2.   [] ← +∞
3.   [] ← 
4. [] ← 0

(, , )
1.  [] > [] + (, ) ℎ
2.   [] ← [] + (, ) //aggiorna il peso del cammino da  a 
3.   [] ←  //aggiorna il predecessore

(, , )
1. __(, )
2.  ← ∅ //insieme dei vertici già estratti
3.  ← [] //vertici da estrarre
4. ℎ  ≠ ∅ 
5.    ← _()
6.    ←  ∪ {} // S si riempie
7.    ℎ  ∈ [] 
8.     (, , (, ))

Esempio

Grafo di test con sorgente = 1
  1. V(G) = {1};
    1. (1,2), π(2) = NIL → 1, d(2) = ∞ → 2;
    2. (1,3), π(3) = NIL → 1, d(3) = ∞ → 4
  2. V(G) = {1, 2, 3};
    1. i nodi esplorati sono:
      1. π(1) = NIL, d(1) = 0
      2. π(2) = 1, d(2) = 2
      3. π(3) = 1, d(3) = 4
    2. (2, 4), π(4) = NIL → 2, d(4) = ∞ → d(2) + 7 = 9
    3. (2, 3), π(3) = 1 → 2, d(3) = 4 → d(2) + 1 = 3
    4. (3, 5), π(5) = NIL → 3, d(5) = ∞ → d(3) + 3 = 6
  3. V(G) = {1, 2, 3, 4, 5}
    1. i nodi esplorati sono:
      1. π(1) = NIL, d(1) = 0
      2. π(2) = 1, d(2) = 2
      3. π(3) = 2, d(3) = 3
      4. π(4) = 2, d(4) = 9
      5. π(5) = 3, d(5) = 6
    2. (5, 4), π(4) = 2 → 5, d(5) = 9 → d(5) + 2 = 8
    3. (5, 6), π(6) = NIL → 5, d(6) = ∞ → d(5) + 5 = 11
    4. (4, 6), π(6) = 5 → 4, d(6) = ∞ → d(4) + 1 = 10

Bellman-Ford

Gli amici Bellman e Ford vogliono raggiungere nel tempo/spazio minore un vertice partendo da un altro vertice, ma in un grafo che può avere pesi negativi.

Uno dei motivi per cui i grafi con pesi negativi sono più incasinati di quelli con pesi solo positivi è che se c'è un ciclo e il suo bilancio è negativo (es. a→b = +2, b→a = -5) per ridurre il peso del cammino basta ciclare all'infinito il loop.

L'algoritmo è piuttosto semplice: per ogni vertice per ogni arco applica il rilassamento; poi controlla che per ogni arco il suo peso sia minore o uguale della somma del vertice più l'arco che li congiunge. In caso contrario è di fronte a un cappio con bilancio negativo e l'algoritmo si ferma restituendo falso.

Il costo dipende dal tipo di grafo, se sparso o denso:

Grafo sparso Grafo denso
Dijkstra - Array lineare O(n2) O(n2)
Dijkstra - Heap binario O(n log n) O(n2 log n)
Bellman-Ford O(n2) O(n3)
_(, , )
1. __(, )
2.   = 1  |[]| − 1 
3.    ℎ (, ) ∈ [] 
4.     (, , (, ))
5.  ℎ (, ) ∈ [] 
6.    [] > [] + (, ) ℎ
7.      
8.  

Floyd-Warshall

Gli amici Floyd e Warshall vogliono raggiungere nel tempo/spazio minore qualunque vertice partendo da un altro vertice qualunque, cioè vogliono calcolare tutti i percorsi minimi possibili.

In modo simile a una matrice M di adiacenza, creano una matrice n*n tale con w: E→R che per ogni cella i,j:

  • se i == j allora M[i, j] = 0
  • se i != j e (i, j) è un arco, allora M[i, j] = w(i, j)
  • se i != j e (i, j) non è un arco, allora M[i, j] = ∞

Per ogni vertice controllano se la somma di ciascun vertice entrante più ciascun vertice uscente ha un peso minore dell'arco diretto o del valore calcolato precedentemente.

Il costo spaziale di questo algoritmo è n2, perché abbiamo bisogno di iniziare con quella che - di fatto - è una matrice nxn di adiacenza. Il costo temporale dell'algoritmo è n3, perché per ogni arco (compresi quelli con valore ∞, cioè compresi gli archi "assenti", che quindi corrispondono a ogni coppia nxn) dobbiamo iterare ogni vertice.

Esempio

La matrice di partenza richiede che siano valorizzati tutti gli archi e che gli "auto-archi" siano impostati a zero.

A
DA 1 2 3 4
1 0
2 0
3 0
4 0

Gli archi da nodo verso se stesso sono impostati a zero

1 2 3 4
1 0 3 7
2 8 0 2
3 5 0 1
4 2 0

Gli altri archi sono riportati (senza calcoli). Gli archi rimanenti, che non esistono, sono impostati a infinito.

Passaggio vertice 1: si riportano gli zeri, tutta la riga 1 e tutta la colonna 1, poiché rappresentano archi diretti che non è neccessario calcolare.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 7
2 8 0
3 5 0
4 2 0

Ora cerchiamo di calcolare il cammino da 2 a 3. L'arco diretto riporta il peso 2, dobbiamo capire se arrivare da 2 a 3 passando per 1 è più conveniente. (2,1) pesa 8, (1, 3) pesa infinito, 8+∞ = ∞, quindi ci conviene tenere l'arco diretto.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 7
2 8 0 2
3 5 0
4 2 0

Ora cerchiamo di calcolare il cammino da 2 a 4. L'arco diretto riporta il peso ∞, dobbiamo capire se arrivare da 2 a 4 passando per 1 è più conveniente. (2,1) pesa 8, (1, 4) pesa 7, 8+7 = 15, quindi ci conviene passare per 1.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 7
2 8 0 2 15
3 5 0
4 2 0

Da 3 a 2 l'arco diretto è ∞, mentre passando per 1 è 5+3 = 8, quindi cambiamo in 8.

Da 3 a 4 l'arco diretto è 1, mentre passando per 1 è 5+7 = 12, quindi teniamo 1.

Da 4 a 2 l'arco diretto è ∞, mentre passando per 1 è 2+3 = 5, quindi cambiamo in 5.

Da 4 a 3 l'arco diretto è ∞, mentre passando per 1 è 2+∞ = ∞, quindi lasciamo ∞.

Il passaggio "vertice 1"
1 2 3 4
1 0 3 7
2 8 0 2 15
3 5 8 0 1
4 2 5 0

Partendo da questa tabella, si ripete per gli altri tre vertici.

_()
1.  ← [] //calcolo il numero di righe, ovvero il numero di vertici
2. 0 = 
3.   = 1  
4.     = 1   
5.       = 1   
6.       [,]() = min([,](−1) + [,](−1), [](−1))
7.  

Alberi di copertura

Definizioni

Taglio

Un taglio è una suddivisione dell'insieme dei vertici V in due sottoinsiemi tali che V1∈G1 e V2∈G2, inoltre V1∩V2 = ∅ e V1∪V2 = V.

Attraversamento

Un arco E attraversa un taglio se E(u, v) con u∈G1 e v∈G2 cioè se i due vertici appartengono ciascuno a uno dei due insiemi determinati dal taglio.

Rispetto

Dato un sottoinsieme di vertici A ⊆ G si dice che un taglio rispetta l'insieme se nessuno dei suoi archi lo attraversa.

Arco leggero

Si dice leggero l'arco (o gli archi) che, dato un insieme di archi con una proprietà, ha il valore minimo per quella proprietà. Tipicamente si usa chiamare arco leggero quello con valore più basso tra quelli che attraversano un taglio.

Arco sicuro

Dato un grafo G con un taglio (S, V-S), un insieme A che sia rispettato dal taglio, un arco leggero che attraversa (S, V-S) è detto sicuro.

MST

Sta per Minimum Spanning Tree, o albero di copertura minimo. Rappresenta l'albero i cui archi sono quelli meno pesanti possibile.

Teorema fondamentale dei MTS

SIa G = (V, E) un grafo non orientato e connesso e sia w: E → R. Siano inoltre date le seguenti ipotesi:

  • A è un insieme di archi tale che A ⊆ E e che A ⊆ MST (che chiameremo T)
  • sia (S, V\S) un taglio che rispetta A, ovvero il taglio non attraversa alcun arco di A o viceversa;
  • sia (u,v) ∈ E, tale che sia leggero e che attraversa il taglio (S, V\S), ovvero che sia quello di peso minimo tra gli archi che attraversano il taglio

Allora l'arco (u,v) è sicuro per A.

Kruskal

L'algoritmo di Kruskal crea tanti alberi quanti sono i vertici, poi li unisce se non fanno parte della stessa foresta. L'unione avviene ordinando gli archi per peso dal più piccolo, così quando (se) avviene l'unione si memorizza l'arco sicuro di volta in volta.

  1. A = ∅; inizializza un insieme vuoto
  2. for each v in V, MAKE_SET(v); per ogni vertice nell'insieme dei vertici crea un albero (qui chiamato set)
  3. for E order by w; ordina gli elementi di E per peso (w = weight)
  4. for each e(u, v) in E
    1. if FIND_SET(u) ≠ FIND_SET(v); se non appartengono allo stesso albero
      1. A ← A ∪ {(u,v)}; si aggiunge l'arco all'insieme degli archi
      2. UNION(u, v); ora u e v fanno parte dello stesso albero
    2. ; se u e v appartengono allo stesso set non fa niente, perché appartengono già allo stesso albero

Domande

L'algoritmo converge? Sì, perché è composto solo da due cicli for, che per definizione convergono.

L'algoritmo è corretto? Sì, perché rispecchia quello che prescrive il teorema master degli MST.

Qual è la complessità dell'algoritmo?

1: O(1)

2: Θ(v) // inizializzazione

3: O(a log a) // ordinamento

4: O(a) // ciclo for

4.1: O(log a) // find set

4.2: O(1) // union

O(1) + O(v) + O(a log a) + O(a log a) + O(1) ⇒ O(a log a), dato che a domina su n e 1 è costante

Prim

L'algoritmo di Prim utilizza due strutture dati aggiuntive: per ogni vertice aggiunge un'informazione sul vertice "padre" π(v) e inserisce ogni vertice in un min-heap binario.

Inizializza tutti i vertici in modo che il loro peso sia ∞ e che i padri siano tutti NIL.
Poi estrae il vertice "root" e assegna 0 come peso.

A questo punto il vertice root non è più presente nell'heap (l'estrazione da un heap binario ha costo di Θ(n)).
A ogni vertice adiacente viene assegnato un peso pari all'arco che lo congiunge al nodo corrente, a meno che il vertice non abbia già un peso e che questo sia minore dell'arco.
Si estrae dall'heap l'elemento minore o - a parità di peso - uno a caso tra gli elementi minori.
Potrebbe succedere che lo stesso vertice sia visitato più volte, e che in una visita successiva l'arco abbia un peso minore di quello già attribuito al vertice. In questo caso, il vertice "cambia di padre" e gli viene assegnato il nuovo peso.
L'algoritmo di Prim è quindi

  1. Q ← V(G) // assegno all'heap i vertici di G
  2. foreach u ∈ Q, key(u) = ∞
  3. key(r) = 0