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