In Java, please complete section: **** TO DO ****

In Mst class, create a minimum spanning tree algorithm that takes and calculates the reference and the weight cost from an undirected graph and weighted graph.

//***Edge class*** public class Edge { private Vertex src; private Vertex dest; private int weight;

public Edge(Vertex src, Vertex dest, int weight) { this.src = src; this.dest = dest; this.weight = weight; }

public Vertex getSrc() { return src; } public Vertex getDest() { return dest; } public int getWeight() { return weight; } @Override public boolean equals(Object o) { Edge e = (Edge) o; if (this.src.equals(e.dest) && this.dest.equals(e.src) && this.weight == e.weight) { return true; } return false; }

@Override public int hashCode() { return this.src.hashCode() + this.dest.hashCode() + this.weight; }

@Override public String toString() { return "(" + this.src.toString() + "," + this.dest.toString() + ") = " + weight; } } //***Graph class*** public class Graph {

private Map> adjVertices = new HashMap<>();

public void addVertex(Integer label) { adjVertices.putIfAbsent(new Vertex(label), new ArrayList<>()); }

public void addEdge(Integer srcInt, Integer destInt, int weight) { Vertex src = new Vertex(srcInt); Vertex dest = new Vertex(destInt);

addEdge(src, dest, weight); addEdge(dest, src, weight); }

private void addEdge(Vertex u, Vertex v, int w) { List uvwList = adjVertices.get(u); Edge uEdge = new Edge(u, v, w); if (!uvwList.contains(uEdge)) { uvwList.add(new Edge(u, v, w)); } }

@Override public String toString() { StringBuilder sb = new StringBuilder(); for (Map.Entry> entry : adjVertices.entrySet()) { sb.append(entry.getKey()).append(":") .append(entry.getValue()).append(" "); } return sb.toString(); }

} //***Union class*** public class Union { private int[] nodes;

public Union( int nodeCount ) { nodes = new int[ nodeCount ]; for( int i = 0; i < nodes.length; i++ ) { nodes[ i ] = -1; } } public void unionHeight( int rootA, int rootB ) { if(nodes[rootB] < nodes[rootA]) { // root2 is deeper nodes[rootA] = rootB; // make root2 the new root } else { if( nodes[rootA] == nodes[rootB]) { nodes[rootA]--; // update height if same } nodes[rootB] = rootA; // make root1 new root } } public void union( int root1, int root2 ) { nodes[ root2 ] = root1; } public int find( int k ) { if( nodes[k] < 0) { return k; } else{ return nodes[k] = find(nodes[k]); } }

public String toString() { StringBuilder sb = new StringBuilder(); sb.append("[ "); for(int i = 0; i < nodes.length; i++) { sb.append(nodes[i]).append(" "); } sb.append("]"); return sb.toString(); } } //***Vertex class*** public class Vertex { int key; public Vertex( Integer key ) { this.key = key; } public Vertex( Vertex v ) { this.key = v.key; } public int getKey() { return key; }

@Override public boolean equals( Object obj ) { Vertex dest = (Vertex) obj; return this.key == dest.key; }

@Override public int hashCode() { Integer il = key; return il.hashCode(); } @Override public String toString() { return String.valueOf(key); } } //***TO DO***Mst class public class Mst { // *** TODO - cost of minimum-spanning tree *** private static int cost = 0; private static Set mst = null;

// *** TODO - Calculate and return the cost *** // of the minimum-spanning tree public static int getMstCost() { return cost; }

public static Set getMst() { return mst; }

// *** TODO - Kruskal's algorithm *** public static Set Kruskals(Graph g) { Set mst = new LinkedHashSet<>(); cost = 0; return mst; } }

//***Main Driver***KruskalsAlgo class public class KruskalsAlgo {

public static void main(String[] args) { Graph graph = new Graph(); createGraph(graph); System.out.println(graph); Mst.Kruskals(graph);

System.out.println("Kraskal's Algorithm:"); System.out.println(Mst.getMst()); } private static void createGraph( Graph g ) { g.addVertex(0); g.addVertex(1); g.addVertex(2); g.addVertex(3); g.addVertex(4); g.addVertex(5); g.addEdge(1,2,1); g.addEdge(0,1,1); g.addEdge(3,2,1); g.addEdge(0,3,1); g.addEdge(5,3,1); g.addEdge(4,1,1); g.addEdge(5,4,1); } private static void UnionTest() { Union testSet6 = new Union(6); System.out.println("initial:" + testSet6);

testSet6.union(4, 5); System.out.println("testSet6 union(4,5):" + testSet6);

testSet6.union(4, 3); System.out.println("testSet6 union(4,3):" + testSet6);

testSet6.union(3, 4); System.out.println("testSet6 union(3,4):" + testSet6); int fnd = testSet6.find(6); System.out.println("testSet6 find(6):" + fnd); System.out.println("testSet6 find(6):" + testSet6); } }