Please code in Java and add comments for my understanding. A start-up code is given to implement the Kruskal function (feel free to change the two prim's algorithm functions in Graph.Java to kruskal's). Please test out the Kruskal implementation in Main.Java (test 1 and test 2), and don't copy-paste old answers. Thanks!

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() } 

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