Please code in Java and add comments for my understanding. Start-up code is provided below (part 1 of this task was to apply prim's algorithm, but please focus on applying given code for kruskal algorithm). Thanks!

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

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

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

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

return -1;

else 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), (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);

// // 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