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)
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 betweennodeCount
& 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 verticesoutputMessage
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
- 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