Order Now  +1 678 648 4277 

Kruskal’s Algorithm Implementation in Java Homework Help

The goal of this task was to implement Kruskal’s algorithm in Java or Python (Java language was chosen). First of all, to complete this assignment, our Java homework helpers had to use the appropriate Java structure for graph representation. Then it was necessary to implement the Kruskal algorithm for search the minimum-spanning-tree of the graph (the graph must be read from the input file) using the approach of disjoint sets. After execution application must output information of found spanning tree and its cost.

Illustrating the Minimum Spanning Tree of a Graph using Disjoints

Graph.java import java.io.File; import java.io.IOException; import java.text.MessageFormat; import java.util.*; public class Graph { /** * Number of vertices in a graph */ private final int n; /** * List of edges of the graph */ private final List edges; /** * Graph constructor, creating a graph instance from a file * * @param fileName to read graph instance from */ public Graph(String fileName) { // opening file for reading using a scanner try (Scanner scanner = new Scanner(new File(fileName))) { // reading first line - number of vertices n = Integer.parseInt(scanner.nextLine()); // creating an empty list of graph edges edges = new ArrayList<>(); // reading line-by-line until the file is over while (scanner.hasNextLine()) { // reading next line String line = scanner.nextLine(); // skipping empty lines if (line.isEmpty()) { continue; } // splitting line content with spaces. Normally it must be split into 3 parts // 1st edge endpoint, 2nd edge endpoint, and edge weight String[] parts = line.trim().split("[\\s]+"); // reading first endpoint int a = Integer.parseInt(parts[0]); // reading second endpoint int b = Integer.parseInt(parts[1]); // reading weight int w = Integer.parseInt(parts[2]); // saving edge to edge list edges.add(new Edge(a,b,w)); } } catch (IOException e) { // throwing an exception on any file reading errors throw new RuntimeException(e); } } /** * Inner class for representing the edge of the graph */ private static class Edge { /** * First endpoint of edge */ private final int v1; /** * Second endpoint of edge */ private final int v2; /** * Weight of edge */ private final int weight; /** * All-parameters constructor * @param v1 first endpoint * @param v2 second endpoint * @param weight of the edge */ public Edge(int v1, int v2, int weight) { this.v1 = v1; this.v2 = v2; this.weight = weight; } /** * Endpoints getter method * @return endpoints of an edge as an array */ public int[] endpoints() { return new int[]{v1,v2}; } /** * Getter for weight field * @return weight of the edge */ public int getWeight() { return weight; } /** * Overridden toString method * @return string representation of edge */ @Override public String toString() { return MessageFormat.format("({0},{1})", v1, v2); } } /** * Method for outputting information about minimum spanning tree of a graph */ public void minimumSpanTree() { List copy = new ArrayList<>(edges); // sorting edges by weight copy.sort(Comparator.comparing(Edge::getWeight)); // creating a disjoint set for graph vertices DisjointSet disjointSet = new DisjointSet(n); // set, containing minimum spanning tree edges Set spanningTree = new HashSet<>(); // cumulating total weight of spanning-tree int totalWeight = 0; // iterating over graph edges in order of ascending weights for (Edge edge: copy) { // getting endpoints int v1 = edge.endpoints()[0]; int v2 = edge.endpoints()[1]; // we skip edge (and not taking it to the final tree) // if adding this edge to the tree makes a cycle // in terms of Disjoint set: two endpoints are in the same set if (disjointSet.detectCycle(v1, v2)) { continue; } // otherwise, adding edge to the final set spanningTree.add(edge); // union corresponding sets of endpoints disjointSet.union(disjointSet.find(v1), disjointSet.find(v2)); // adding weight totalWeight += edge.getWeight(); } // outputting MST info System.out.println("Minimum Spanning Tree contains following edges:"); for (Edge e : spanningTree) { System.out.println(e); } System.out.println("Total Minimum Spanning Tree weight is " + totalWeight); } private static class DisjointSet { private final List nodes; public DisjointSet(int totalNodes) { nodes = new ArrayList<>(totalNodes); for (int i = 0; i < totalNodes; i++) { nodes.add(new DisjointSetEntry(i)); } } public int find(int node) { int parent = nodes.get(node).getParent(); if (parent == node) { return node; } else { return find(parent); } } public void union(int root1, int root2) { DisjointSetEntry entry = nodes.get(root1); entry.setParent(root2); } public boolean detectCycle(int u, int v) { return find(u) == find(v); } } private static class DisjointSetEntry { private int parent; DisjointSetEntry(int parent) { setParent(parent); } public int getParent() { return parent; } public void setParent(int parent) { this.parent = parent; } } public static void main(String[] args) { Graph graph = new Graph("input.txt"); graph.minimumSpanTree(); } }