Algoritmo di Prim

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 .

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.

Prim(G,w,s)_init

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

Prim(G,w,s)_build

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 mantiene la seguente invariante di 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 e

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
Extract_Min
Decrease_Key
\

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 si ha . 

Inoltre , e poiché è una funzione decrescente, avremo:

Pertanto , per

Inoltre:

Il grafo ha una certa densità, cioè non è definibile molto sparso.

Dimostrazione: