MSTree PrimMST(Graph g)
{
MST = empty graph (nV(g))
usedV = {0}; unusedE = edges(g)
while (size(usedV) < nV(g)) {
find (edge e in unusedE) satisfying {
e = (s,t,w), s ∈ usedV, t ∉ usedV,
w is min weight of all such edges
}
add e = (s,t,w) to MST
usedV += t; unusedE -= e
}
return MST
}
|