Implement Bonus Section ONLY (the rest is just background information). A start-up code is given to implement the Kruskal function (change the two prim's algorithm functions in Graph.Java to kruskal's). Please test the Kruskal implementation in Main.Java (test 1 and test 2), and post a screenshot of the output. Thanks!

Background Info ----------------------------------------------------------------------------------------------------------------------------------------------------------------------

BONUS SECTION ---------------------------------------------------------------------------------------------------------------------------------------------------------------------------------

1) 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  prim(Node s) { // implement this } // prim() //----------------------------------------------- public List primPQ(Node s) { // implement this } // primPQ() } // class Graph 

2) 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  otherNode.priority) return 1; else return 0; } @Override public String toString() { String s = "N" + this.name; return s; } } // class Node 

3) 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  otherEdge.weight) return 1; else return 0; } } // class Edge 

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), (5, 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); // // grad assignment // System.out.println(); // System.out.println("now call kruskal()"); // edges = G.kruskal(); // 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() }

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. 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. Students taking the course for graduate credit, and undergraduates for a little bit of extra credit: implement Kruskal's Algorithm, using the union-find data structure. Implement this in a function called public List kruskal () . To determine whether the addition of an edge e from ni to nj to (V,T) would create a cycle, check to see whether ni and nj are in the same connected component, using the union-find data structure. Ask me for help with the implementation of the union-find data structure. 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