Kruskal's Algorithm Minimum Spanning Tree (Graph MST)

Java Implementation of Kruskal's Algorithm using disjoing sets
Kruskal's algorithm: Start with T = ∅. Consider edges in ascending order of weight. Insert edge e into T unless doing so would create a cycle.

Works on UN-directed graphs
Algorithm still works on edges with identical weight
Edges are sorted by weight first. Depending on the order they are entered into the edge list in the constructor, you may get different Minimum Spanning Trees (but all still optimal solutions)

PseudoCode

Detailed Implementation

Code Notes

Current code runs on this sample graph It produces this Minimum Spanning Tree

Requires distinct nodes named with consecutive integers. If they really do have the same "name", convert them to integer ID's to use this algorithm
Example graph has 8 nodes numbered 1-8 (array ignores the 0th index)
Graph is created as an Edge List
Make sure nodeCount is accurate. There's no error checking between nodeCount & the actual edge list
DisjointSet nodeSet = new DisjointSet(nodeCount+1); skips the 0th index by creating a Disjoint Set 1 larger than the number of vertices
outputMessage is a string that records the steps the algorithm takes. It's printed to the screen & to a file once complete
My implementation has early termination (A Spanning Tree of a graph has N-1 edges so the algorithm stops whenn it has added N-1 Edges) Hence && mstEdges.size()<(nodeCount-1) in my loop
The Edge class simply packages an edge's weight & 2 vertices together as 1 object

Sources

Disjoint Sets by Mark Allen Weiss Author of Data Structures and Algorithm Analysis in Java (3rd Edition), 2011
He also has other helpful Java Data Structures implementations

kruskals-algorithm-minimum-spanning-tree-mst's People