Prim Algorithm

public class MSTByPrim
{
public Graph computeMST(Graph inputGraph)
{
VertexSet touchedVertices = new VertexSet();
EdgeSet keptEdges = new EdgeSet(touchedVertices);
Iterator itGN = inputGraph.getVertexSet().iterator();
if (itGN.hasNext())
{
touchedVertices.add((Vertex)itGN.next());
}
while (touchedVertices.size() < inputGraph.getVertexSet().size())
{
Iterator itTN = touchedVertices.iterator();
int minLength = Integer.MAX_VALUE;
Edge bestCandidate = null;
Vertex neighborToAdd = null;
while (itTN.hasNext())
{
Vertex current = (Vertex)itTN.next();
VertexSet neighbors = (VertexSet)current.getNeighbors(inputGraph);
Iterator itN = neighbors.iterator();
while (itN.hasNext())
{
Vertex currentNeighbor = (Vertex)itN.next();
// we are only interested in outgoing edges
if (!touchedVertices.contains(currentNeighbor))
{
EdgeSet potentialMSTEdges = (EdgeSet)
current.getEdgesTo(inputGraph,currentNeighbor);
Iterator itpMSTe = potentialMSTEdges.iterator();
Edge potentialEdge = null;
// try every edge in the edgeset

while (itpMSTe.hasNext())
{
potentialEdge = (Edge)itpMSTe.next();
// if the current edge is the best up to now
if (Integer.parseInt(potentialEdge.getValue("length"))<
minLength)
{
minLength =
Integer.parseInt(potentialEdge.getValue("length"));
bestCandidate = potentialEdge;
neighborToAdd = currentNeighbor;
}
}
}
}

}
touchedVertices.add(neighborToAdd);
keptEdges.add(bestCandidate);
}

return new Graph(touchedVertices,keptEdges);
}
}