Please code in Java and add comments for my understanding. Instructions, Pseudo code, and Start-up code is given to implement Prim's Algorithm. Thanks!

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

Pseudo Code:

---------------------------------------------------------------------------------------- Start-up Code -----------------------------------------------------------------------------------------------------------------------------------

1) Node.Java

import java.util.List;

import java.util.ArrayList;

import java.lang.Comparable;

public class Node implements Comparable {

List adjlist;

int name;

int priority; // needed for PQ implementation

public Node(int name) {

this.name = name;

this.adjlist = new ArrayList();

this.priority = 0;

}

public void add(Edge edge) {

this.adjlist.add(edge);

}

// this is needed for PQ implementation

public int compareTo(Object o) {

Node otherNode = (Node) o;

if (this.priority

return -1;

else if (this.priority > otherNode.priority)

return 1;

else

return 0;

}

@Override

public String toString() {

String s = "N" + this.name;

return s;

}

} // class Node

***********************************************************************************************

2) Edge.Java

public class Edge {

int weight;

Node n1;

Node n2;

public Edge(Node n1, Node n2, int weight) {

this.n1 = n1;

this.n2 = n2;

this.weight = weight;

}

@Override

public String toString() {

String s = "(" + this.n1.name + ", " + this.n2.name + "); wt = " + this.weight;

return s;

}

// needed only for grad assignment

public int compareTo(Object o) {

Edge otherEdge = (Edge) o;

if (this.weight

return -1;

else if (this.weight > otherEdge.weight)

return 1;

else

return 0;

}

} // class Edge

****************************************************************************************

3) Graph.Java

import java.util.List;

import java.util.ArrayList;

import java.util.PriorityQueue;

public class Graph {

List nodes;

//---------------------------------------------------

public Graph() {

nodes = new ArrayList();

}

//---------------------------------------------------

public void addNode(Node node) {

for (Node n: this.nodes) {

if (n == node) {

System.out.println("ERROR: graph already has a node " + n.name);

assert false;

}

}

this.nodes.add(node);

}

//---------------------------------------------------

public void addEdge(Node n1, Node n2, int weight) {

// outgoing edge

int idx1 = this.nodes.indexOf(n1);

if (idx1

System.out.println("ERROR: node " + n1.name + " not found in graph");

assert false;

}

int idx2 = this.nodes.indexOf(n2);

if (idx2

System.out.println("ERROR: node " + n2.name + " not found in graph");

assert false;

}

Edge e1 = new Edge(n1, n2, weight);

this.nodes.get(idx1).add(e1);

Edge e2 = new Edge(n2, n1, weight);

this.nodes.get(idx2).add(e2);

}

//-----------------------------------------------

public List prim(Node s) {

// implement this

} // prim()

//-----------------------------------------------

public List primPQ(Node s) {

// implement this

} // primPQ()

} // class Graph

*************************************************************************************************************

4) Main.Java

import java.util.List;

public class Main {

public static void main(String args[]) {

testOne();

testTwo();

}

// From the lecture slides.

// Starting at node 10, here are the edges that form an MST:

// (10, 8), (8, 5), (5, 2), (2, 1), (1, 3), (3, 4), (3, 6),

// (2, 9), (6, 7); the total weight is 54

// Your function should select nodes in this order:

// 10, 8, 5, 2, 1, 3, 4, 6, 9, 7

public static void testOne() {

System.out.println("this is testOne()");

Node n1 = new Node(1);

Node n2 = new Node(2);

Node n3 = new Node(3);

Node n4 = new Node(4);

Node n5 = new Node(5);

Node n6 = new Node(6);

Node n7 = new Node(7);

Node n8 = new Node(8);

Node n9 = new Node(9);

Node n10 = new Node(10);

Graph G = new Graph();

G.addNode(n1);

G.addNode(n2);

G.addNode(n3);

G.addNode(n4);

G.addNode(n5);

G.addNode(n6);

G.addNode(n7);

G.addNode(n8);

G.addNode(n9);

G.addNode(n10);

G.addEdge(n1, n2, 1);

G.addEdge(n1, n3, 2);

G.addEdge(n2, n3, 4);

G.addEdge(n2, n4, 21);

G.addEdge(n2, n5, 6);

G.addEdge(n2, n9, 9);

G.addEdge(n3, n4, 5);

G.addEdge(n3, n6, 8);

G.addEdge(n4, n5, 12);

G.addEdge(n5, n6, 7);

G.addEdge(n5, n8, 3);

G.addEdge(n5, n9, 20);

G.addEdge(n6, n7, 11);

G.addEdge(n6, n10, 13);

G.addEdge(n7, n8, 14);

G.addEdge(n8, n9, 16);

G.addEdge(n8, n10, 10);

System.out.println("first call prim()");

List edges = G.prim(n10);

for (Edge e: edges)

System.out.println(e);

System.out.println();

System.out.println("now call primPQ()");

edges = G.primPQ(n10);

for (Edge e: edges)

System.out.println(e);

} // testOne()

public static void testTwo() {

System.out.println("this is testTwo()");

Node n1 = new Node(1);

Node n2 = new Node(2);

Node n3 = new Node(3);

Node n4 = new Node(4);

Node n5 = new Node(5);

Graph G = new Graph();

G.addNode(n1);

G.addNode(n2);

G.addNode(n3);

G.addNode(n4);

G.addNode(n5);

G.addEdge(n1, n2, 4);

G.addEdge(n1, n4, 6);

G.addEdge(n1, n5, 9);

G.addEdge(n2, n3, 12);

G.addEdge(n2, n4, 11);

G.addEdge(n3, n4, 5);

G.addEdge(n3, n5, 10);

G.addEdge(n4, n5, 2);

System.out.println("first call prim()");

List edges = G.prim(n5);

for (Edge e: edges)

System.out.println(e);

System.out.println();

System.out.println("now call primPQ()");

edges = G.primPQ(n5);

for (Edge e: edges)

System.out.println(e);

} // testTwo()

}

*************************************************************************************

5) PQexample.Java (Reference for Section 1.4)

import java.util.PriorityQueue;

public class PQExample {

public static void main(String args[]) {

PQtest();

}

public static void PQtest() {

PriorityQueue PQ;

PQ = new PriorityQueue(20);

// each entry in the queue is a Thing;

// they'll be put in the queue in priority order

Thing t1 = new Thing("Audi", 5);

PQ.add(t1);

Thing t2 = new Thing("Civic", 10);

PQ.add(t2);

Thing t3 = new Thing("Outback", 2);

PQ.add(t3);

Thing t4 = new Thing("Tesla", 12);

PQ.add(t4);

while (PQ.size() > 0) {

Thing t = PQ.poll();

System.out.println("popped this thing: " + t);

}

System.out.println();

// now same experiment, but this time also changing

// the priorities of items in the queue ("updating keys")

PQ.add(t1);

PQ.add(t2);

PQ.add(t3);

PQ.add(t4);

t2.updatePriority(1);

// must explicitly call updatePQ()

updatePQ(PQ);

while (PQ.size() > 0) {

Thing t = PQ.poll();

System.out.println("popped this thing: " + t);

}

}

//-----------------------------------------------------

// this is a static because it's in Main

public static void updatePQ(PriorityQueue pq) {

Object arr[] = pq.toArray();

pq.clear();

for (int i=0; i

Thing t = (Thing) arr[i];

pq.add(t);

}

}

}

***********************************************************************************

6) Thing.Java (Reference for Section 1.4)

public class Thing implements Comparable {

private String name;

private int priority;

public Thing(String name, int priority) {

this.name = name;

this.priority = priority;

}

public void updatePriority(int newPriority) {

this.priority = newPriority;

}

public int compareTo(Object o) {

Thing otherThing = (Thing) o;

if (this.priority

return -1;

else if (this.priority > otherThing.priority)

return 1;

else

return 0;

}

@Override

public String toString() {

String s = this.name + " (" + this.priority + ")";

return s;

}

}

You'll implement Prim's Algorithm for finding a minimum spanning tree in an undirected, weighted graph. You may work alone or with a partner. Graduate students, and undergraduates doing the graduate work for extra credit, must work individually. 1.1 Data Structures I will give you use Node, Link, and Graph classes. As before, the graph will be represented as an adjacency list. Only now, since each edge also has a weight, the entries in the adjacency list for a node will be an instance of Link: a record containing a node and a weight. (We're still working with an undirected graph, and so a Link suffices to show the connection between two nodes.) Do not make any changes to Node. java or Link. java. For convenience, we will maintain an edge between a node u and a node v as a link in the adjacency list for u and a link in the adjacency list for v. 1.2 Functions Implement these two function on Graph: public List prim(Node s); public List primPQ(Node s); Each will use Prim's algorithm to find a minimum spanning tree and will return the edges found. The first function will do this navely, looking at each iteration for the min-cost edge from a node that has already been visited and then using the node at the other end of that edge as the next node chosen. The algorithm itself is straightforward: set totalWeight to zero initialize the list S to be empty add the initial node s to S while S does not contain every node of G{ select the edge e of lowest cost that connects a node in S and a node v that is not in S save the edge e to the list of edges add v to S totalWeight = totalWeight + the weight the selected edge Print out the total weight. The selection of which edge to add is the key step: for the nave implementation, look at all all edges incident to nodes already in S, and of those edges, consider the ones that are incident to a node not already in S. The second function will use a priority queue to determine the next edge (and node) to be chosen. In the PQ implementation, just take the node at the front of the queue (since the queue will be maintained with nodes sorted by appropriate edge weight). The key think for this implementation is that when you select a node from the priority queue, you won't know which specific edge led you to that node; in other words what the next lowest-cost edge is. I save that information in a separate data structure ("edgeFor[node]").For the priority-queue implementation, do this: set totalWeight to zero mark all nodes as not selected set the priority for s to zero set the priority for every node except for s to be a large value put every node in the priority queue while s does not contain every node of G{ get the first node u in PQ for each node v adjacent to u that I haven't already selected \{ if the weight of the edge (u, v) is less than the priority of v{ set the priority of v to the weight of the edge (u, v) // in the future, when I pick v from the queue, I will also need // to know which edge got me to v: save this information record that the edge to v is the edge (u, v) \} call updatePQ() to update the priority queue (to reflect the new weights) add u to s and mark u as selected save the edge corresponding to u (from my edgeFor [] data structure) totalWeight = totalWeight + the priority of node u Each of your functions should print the total weight of the MST that it computes. 1.4 Priority queues The algorithm for Prim using a priority queue is described on pp. 149-150. [Plus, I'll post some more explanation over the weekend.] I've given you an example of how to use a Java priority queue, in PQexample.java and Thing.java. The Java PriorityQueue does not provide a ChangeKey function. You'll have to rebuild the priority queue explicitly after changing the key value (edge weight, in this case) of any node that is in the queue. I suggest implementing a static void updatePQ (Priorityqueue pq) function in Graph. To rebuild a priority queue after one or more priority values change, dequeue each node and put it into list, and then reinsert each node. The poll() function on a Java priority queue provides the functionality described by the book as ExtractMin. I've also given you a Main class that can use. Main has two test cases, testOne() and testTwo(), on which you can test your functions. Here's the graph from testone(): Since the edges are distinct, your functions should compute the same MST as I show in the comments for testOne(). The graph in testTwo() is simpler, but should show more clearly the updates of the priority values in the priority queue