Programming Language: Java Programming Environment: Eclipse

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.

Refer to Greedy algorithms for the pseudocode for Prims algorithm.

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.

Instruction: edit the TODO part of the code only, every after the "do not edit" comment, don't edit. Make sure the code runs.

---------------------------------------------------------------------------------------------

import java.io.File; import java.io.IOException; import java.util.ArrayList; import java.util.List; import java.util.Scanner;

/* Calculates the minimal spanning tree of a graph rovided below

public class LAB5 {

// TODO document this method

public static void FindMST(Graph g) {

// TODO implement this method

/*Playground:

* The following sniplets of code is provided to ease your life.

* You don't have to use it or look at it.

*/

//V: list of vertices

Vertex[] V = g.getVertices();

//E: list of edges

List E = 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));

}

}

}

/*

* look at my pretty edges:

Edge[] E = g.getEdges();

*/

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

double myInf = Double.POSITIVE_INFINITY;

//sample useage of a PQ:

int[] dist = {20, 30, 10, 5, 333};

IndexMinPQ Q = new IndexMinPQ(dist.length);

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

Q.insert(i, dist[i]);

}

// print each key using the iterator

System.out.println("Priority Queue iterator example:");

for (int i : Q) {

System.out.println(i + " " + dist[i]);

}

}

/********************************************

*

* You shouldn't modify anything past here

*

********************************************/

// reads in an undirected graph from a specific file formatted with one

// x/y node coordinate per line:

private static Graph InputGraph(String file1) {

Graph g = new Graph();

try (Scanner f = new Scanner(new File(file1))) {

while(f.hasNextDouble()) // each vertex listing

g.addVertex(f.nextDouble(), f.nextDouble());

} catch (IOException e) {

System.err.println("Cannot open file " + file1 + ". Exiting.");

System.exit(0);

}

return g;

}

public static void main(String[] args) {

Scanner s = new Scanner(System.in);

String file1;

System.out.printf("Enter ");

System.out.printf("(e.g: points/small1 1.5) ");

file1 = s.next();

// read in vertices

Graph g = InputGraph(file1);

g.epsilon = s.nextDouble();

FindMST(g);

s.close();

System.out.printf("Weight of tree: %f ", g.getTotalEdgeWeight());

}

}