Description
For this assignment you will be implementing the greedy algorithm, “Kruskal’s Algorithm” as described in section 16.2.3 of the course text book. Kruskal’s Algorithm calculates the minimum-spanning-tree of a graph. The algorithm calculates:
- the minimum spanning tree (MST) of the graph
- the sum of the weights of the edges of the MST
The following starter code is provided on canvas:
- java
- java
- java
- java
- java
- java
Implement Kruskal’s Algorithm as a public static method in the MstAlgorithms class. UsingKruskalsAlgorithm contains public static void main. Use it as a guide for how to test your code, as I will be using similar calling sequences when testing your code. You may add to and/or overload the public methods of these classes. But do not remove or alter the existing methods.
MstAlgorithms.Kruskals( Graph g ) is the entry point for your Kruskals Algorithm. It takes as input an undirected, weighted graph, calculates a minimum-spanning tree, and returns it to the calling method. The minimum-spanning tree is a Set of edges. In addition to returning it to the calling method, it saves a reference to it as a private static field in MstAlgorithms (see the starter code). There two getter methods. One returns a reference to the minimum-spanning tree, the other returns its cost. The cost is the sum of the weights in the minimum-spanning tree.
The DisjointSet class is from the text, “Data Structures and Algorithm Analysis in Java”, third edition, by Mark Weiss. It is a simple implementation of the Disjoint class described in chapter 3.1 of the course textbook, “How to Think About Algorithms”, by Jeff Edmonds, in the section titled, “Union-Find Set System”. If you prefer to use your own implementation, feel free to do so. There are a number of good resources on the subject of Disjoint Sets, and Union-Find Set on-line. The key methods used by Kruskal’s Algorithm are:
- Makeset(v)
- Find(v)
- Union(u, v)
These three methods are described in chapter 3.1 of the course text.
In the starter files, please note the packages in which the starter files reside. Please use those same identifiers. When you are finished with your implementation, upload only those files that you modified to canvas. I will be using my own test class with your code.