Pseudocodice

Lezione 4 di 9 del corso Algoritmo di Prim - Algoritmi sui grafi di Coddy.

prim(n, edges):
   inTree[0] = true; everything else false
   total = 0
   repeat (n - 1) times:
      best = the crossing edge (one endpoint in, one out) with smallest weight
      if none exists: stop      # disconnected
      total += best.weight
      inTree[best.outsideEndpoint] = true
   return total

Un arco (u, v, w) attraversa il taglio quando inTree[u] e inTree[v] sono diversi.
Esaminare tutti gli archi a ogni iterazione per trovare l’arco che attraversa il taglio con il costo minore mantiene semplice il codice (non serve una coda di priorità per i grafi piccoli).

Provalo tu

Questa lezione non include una sfida di codice.