Question & Answer: Complete the program by implementing the Prim’s algorithm solution. A priority que…..

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:

Still stressed from student homework?
Get quality assistance from academic writers!