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