PRIM'S ALGORITHM

int prim(graph g, tree& t, node root) 
   vertex v, w
   edge e 
   int treecost  :=  0
   heap h
   t.edges := empty
   t.nodes := {root}
   h.makeheap(g.incident(root))    //  can use repeated inserts
   do (e :=  h.deletemin()) $\neq$ empty     $\rightarrow$ 
      t.edges  :=  t.edges $\cup$ {e} 
      v  := e.new_node
      t.nodes  :=  t.nodes $\cup$ {v}
      treecost  :=  treecost  +  e.cost 
      for w  $\in$  g.adj(v)   $\rightarrow$  
         if  w $\mbox {$\space \; \not \in \; $}$  t.nodes and w $\mbox {$\space \; \not \in \; $}$  h   $\rightarrow$  
            e.old_node := v
            e.new_node := w
            e.cost := g.cost(v, w)
            h.insert(e) 
         | w $\in$ h and g.cost(v,w) < h.cost(w)  $\rightarrow$  
            h.changekey(w, g.cost(v,w), v)
         fi 
      rof  
   od
   return treecost  
end prim