Algoritmo di Prim

Ad ogni passo $T$ è un sottoinsieme di archi dello MST

$S$ = insieme di nodi di $T$

• inizializzazione: pone in $S$ un qualsiasi nodo $u$, il nodo $u$ sarà la radice dello MST
• ad ogni passo aggiunge a $T$ l’arco $(x,y)$ di costo minimo tra tutti quelli che congiungono un nodo $x$ in $S$ ad un nodo $y$ in $V\backslash S$ (scelta greedy)
• termina quando $S=V$

Implementazione dell’algoritmo di Prim con coda a priorità

• mantiene un insieme di vertici esplorati $S$
• per ogni nodo non esplorato $v$, mantiene $a[v]$ = costo dell’arco di costo più basso tra quelli che uniscono $v$ ad un nodo in $S$
• mantiene coda a priorità $Q$ delle coppie $(a[v],v)$ con $v \notin S$

Analisi:

• $O(n^2)$ con array o lista non ordinati
• $O(mlogn+nlogn)$ con heap; siccome nel problema dello MST il grafo è connesso allora $m\geq n-1$ e $O(mlogn+nlogn)=O(mlogn)$