functor PRIM(
structure G :  sig 
   type Vertex type Edge type Graph 
    val adj : Graph -> Vertex -> Edge list 
    val ends: Edge -> Vertex * Vertex
end
   structure VS : SetSig
   structure  T : SetSig
   structure PQ : QueueSig
   sharing type G.Vertex = VS.Item
       and type  PQ.Item = T.Item = G.Edge
) = struct
   type Graph  = G.Graph
   type Vertex = G.Vertex
   type Tree   = T.Set

   fun span (g:Graph) (s:Vertex) : Tree =
   let fun grow edges tree included = 
        if PQ.isEmpty edges then tree else
            let val (e, es) = PQ.deq edges
                val (u, v) = G.ends e
             in
                 if VS.member included v then 
                    grow es tree included
                 else grow
                      (PQ.menq (G.adj g v, es))
                      (T.insert (e, tree)) 
                      (VS.insert (v, included))
            end
    in 
       grow (PQ.menq(G.adj g s, PQ.empty)) 
             T.empty 
            (VS.insert(s,VS.empty))
    end
end;