Complete the program by implementing the Prims algorithm solution. A priority queue (pq) has been

included to minimize the anxiety that can be caused by this assignment.

Greedy algorithms for the pseudocode for Prims algorithm. More information on the pq and the Euclidean graphs is provided below.

The program expects one input:

Graph with the vertices.

The program should return one output:

The graph with the vertices with the MST edges added to it.

// TODO document this method

public static void FindMST(Graph g) {

// TODO implement this method

//V: list of vertices

Vertex[] V = g.getVertices();

//E: list of edges

List E = new ArrayList();

List minSet = new ArrayList();

//add implicit edges to a new list

for (Vertex u: V) {

for (Vertex v: V) {

if (u != v) {

E.add(new Edge(u, v));

}

}

}

//Init all Q[i].key = inf

double myInf = Double.POSITIVE_INFINITY;

//useage of a PQ:

IndexMinPQ Q = new IndexMinPQ(V.length);

for (int i = 0; i < V.length; i++) {

Q.insert(V[i].ID, myInf);

}

while (!Q.isEmpty()) {

int vId = Q.delMin();

Edge lightestEdge = null;

Double edgeWeight = myInf;

for (Edge e : E)

{

if (e.src.ID == vId)

{

if (Q.contains(e.dst.ID))

{

Q.changeKey(e.dst.ID, e.cost);

if (e.cost < edgeWeight)

{

edgeWeight = e.cost;

lightestEdge = e;

}

}

}

}

if (lightestEdge != null) {

g.addEdge(lightestEdge.src,lightestEdge.dst);

}

}

}

I failed some of the Unit tests in the program, not sure where to go from here.