USA: +1 (725) 712-1730 
Sign in
Complete the program by implementing the Prim’s 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 Prim’s 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.
Expert Answer
import java.util.*;
import java.lang.*;
import java.io.*;
class MinSpanTree
{
private static final int Vertices=5;
int minimumKeyss(int keys[], Boolean isSet[])
{
int minimum = Integer.MAX_VALUE, minimumIndex=-1;
for (int vert = 0; vert < Vertices; vert++)
if (isSet[vert] == false && keys[vert] < minimum)
{
minimum = keys[vert];
minimumIndex = vert;
}
return minimumIndex;
}
void dispMST(int roots[], int no, int grph[][])
{
System.out.println(“Edge Weight”);
for (int uu = 1; uu < Vertices; uu++)
System.out.println(roots[uu]+” – “+ uu+” “+
grph[uu][roots[uu]]);
}
void MST(int grph[][])
{
int roots[] = new int[Vertices];
int keys[] = new int [Vertices];
Boolean isSet[] = new Boolean[Vertices];
for (int uu = 0; uu < Vertices; uu++)
{
keys[uu] = Integer.MAX_VALUE;
isSet[uu] = false;
}
keys[0] = 0;
roots[0] = -1; s
for (int cnt = 0; cnt < Vertices-1; cnt++)
{
int qq = minimumKeyss(keys, isSet);
isSet[qq] = true;
for (int vert = 0; vert < Vertices; vert++)
if (grph[qq][vert]!=0 && isSet[vert] == false &&
grph[qq][vert] < keys[vert])
{
roots[vert] = qq;
keys[vert] = grph[qq][vert];
}
}
dispMST(roots, Vertices, grph);
}
public static void main (String[] args)
{
MinSpanTree msts = new MinSpanTree();
int grph[][] = new int[][] {{0, 2, 0, 6, 0},
{2, 0, 3, 8, 5},
{0, 3, 0, 0, 7},
{6, 8, 0, 0, 9},
{0, 5, 7, 9, 0},
};
msts.MST(grph);
}
}
Output:
