Strategia
- Si seleziona un nodo
; - Si esegue
volte la seguente operazione: - si seleziona l’albero
contenente , - si seleziona un arco di costo minimo incidente su
e lo si colora di .
- si seleziona l’albero
Implementazione
Inizializzazione
Terminologia:
Campo ‘key’ del vertice, rappresenta il peso minimo di un arco qualsiasi che collega v a un vertice nell’albero finale MST. Per convenzione, se l’arco non esiste. Padre o predecessore del vertice v nell’albero finale nodo di inizio, start, o la radice dell’albero MST finale.
for (u in V[G]): // per ogni vertice in G
k[u] = +INFTY; // poni tutte le 'key' di ogni vertice a infinito, perché inizialmente tutti i nodi attorno alla radice sono 'sconosciuti'
pred[u] = NIL; // poni tutti i predecessori di ogni nodo a NIL, perché ancora l'albero finale MST è vuoto
k[s] = 0; // poni il campo 'key' della radice a 0. La radice è il primo nodo da visitare
Q = Build-Heap(V[G],k); // Q è una coda di min-priorità che si svuota man mano che costruiamo l'MST finale.
Costruzione
while (Q != EMPTY_SET): // finchè non svuotiamo la coda di min-priorità Q, l'albero MST finale non è completo
u = Extract_Min(Q); // trova il prossimo vertice da considerare: quello con valore 'key' minore
for (v in G.Adj[u]): // il vertice da considerare deve essere adiacente a quello appena processato
if (v in Q) && (w(u,v) < k): // se v è nella coda Q (cioè ancora sconosciuto) e il peso del suo arco è minore della key...
Decrease_Key(Q, v, w(u,v) ); // ...aggiorna la coda,
pred[v] = u; // ... e aggiorna il predecessore del vertice v
return { (pred[v],v) : v in V[G] \ {s} }
Questo ciclo
- I vertici già inseriti nell’MST finale sono quelli che appartengono a
. - Per ogni vertice
, se , allora la key del vertice v è minore di infinito ( ), ed è il peso di un arco leggero tra: che collega a qualche vertice che si trova già nell’MST
Esempio Esercizio:
Per eseguire l’esercizio in maniera “formale”, cioè seguendo strettamente lo pseudocodice, conviene mantenere una tabella a lato del grafo, del tipo:
Vertice | Visitato? | Costo | Percorso |
---|---|---|---|
a | FALSE | -1 | |
b | FALSE | -1 | |
c | FALSE | -1 | |
… | … | … | … |
Esempio di una tabella di inizio. |
Il seguente esercizio è parecchio lungo:
Nota, l’esercizio è leggermente modificato rispetto alla prova d’esame. In particolare, ho cambiato i pesi degli archi
Esempio svolgimento esercizio D'ESAME con Prim (svg)
Consiglio di aprire in un’altra scheda
Complessità
- Inizializzazione:
- Costruzione:
Extract-Min, Decrease_Key.
\ | Heap Binario | Heap Binomiale | Heap di Fibonacci |
---|---|---|---|
Inizializzazione | |||
\ |
Notiamo come l’Heap di Fibonacci non è mai peggiore di altri Heap.
Questo perché ci troviamo nel caso
Confronto tra E logV ←> E + V logV
Quindi
Abbiamo che:
Per
Inoltre
Pertanto
Inoltre:
Dimostrazione: