Pseudo Code

Lesson 4 of 9 in Coddy's Prim's Algorithm - Graph Algorithms course.

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

An edge (u, v, w) crosses the cut when inTree[u] and inTree[v] differ.
Scanning all edges each round to find the cheapest crossing edge keeps the code simple (no priority queue needed for small graphs).

Try it yourself

This lesson doesn't include a code challenge.