Algoritmo di Prim

L'algoritmo trova l'MST partendo da $r\in V$ e propagando la creazione dell'albero sugli archi con pesi minori:

prim(G, w, r)
  Q = G.V  // Coda di minima priorità
  d = {}   // Contiene il peso d[v] più piccolo per la connessione al nodo v
  𝜋 = {}   // Contiene il nodo 𝜋[v] (vicino di v) da cui è originato il peso d[v]
  for each u in G.V
    d[u] = +∞
    𝜋[u] = NIL
  d[r] = 0

  while Q.heap_size > 0
    u = extract_min(Q)  // Sceglie il nodo u con d[u] più piccolo
    for each v in neighbors(G, u)
      if contains(Q, v) and w(u, v) < d[v]
        d[v] = w(u, v)  // Potrebbe causare un riordinamento di Q
        𝜋[v] = u

  A = {}
  for each v in G.V
    e = (𝜋[v], v)
    if contains(G.E, e) and v != r  // Evita 𝜋[v] = 𝜋[r] = NIL
      add(A, e)
  return A

che è corretto perchè rispetta il teorema fondamentale degli MST. Infatti, ad ogni istante, si ha che: $$A=\left\{({\pi }_v,v)\in E|v\in V\setminus Q\setminus \{r\}\right\}$$ e dato che ${\pi }_v\in V\setminus Q$, l'arco $({\pi }_v,v)$ non attraverserà mai il taglio $(V\setminus Q,Q)$, cioè il bordo tra i nodi già visitati e quelli ancora da visitare. Inoltre, il prossimo $u$ proviene sicuramente dall'arco leggero del taglio.

La complessità si ricava con, sapendo che $m\ge n-1$: $$T(n,m)=n+n\log n+\sum _{i=1}^n\mathrm{deg}(u_i)\cdot \log n=O(m\log n)$$ dove, il primo $\log n$ è dato dal costo della extract_min su Q, il $\mathrm{deg}(u_i)$ dalle neighbors(u) iterazioni per il nodo estratto u (che si somma a $2m$ per la stretta di mano) e l'ultimo $\log n$ dall'assegnamento a d[v].

Per esempio, partendo dal nodo $r=1$ nel grafo

i passaggi effettuati dall'algoritmo sono: