Use Algoraph to implement an algorithm called MinimumSpanningTree that returns a minimum spanning tree of a weighted graph.
Your algorithm should extend AbstractAlgorithm.
The output should be the weight of the MST followed by a list of the edges
of the MST in increasing order. E.g. something like:
34;(0,5) (1,3) (2,3) (2,5) (3,4)
Important Note:
The algorithm in the book omits an important detail: The if statement should actually be something like if(cost(z)>w(v,z) && contains(H,z)),
the last part being something more like H.contains(z) in Java.
This part is saying that the neighbor of v is still in the priority queue so that it has not already been added to the tree. If you are getting the incorrect weights on the puzzles Wikipedia, 7Dudes, and WebOfLies3, this is probably your error.
By the way, to get the weight of the edge from vertex from
to vertex to, use the following code
Edge e = Edge.createEdge(from, to);
int weight = puzzle.getWeightForEdge(e);
Important Note: For some reason that I cannot remember, if the edge
does not exist in the graph, getWeightForEdge will return 1.
Thus, you need to know that e is actually an edge before you call
that method since otherwise that method lies to you. If you implement Prim's algorithm correctly, this should not be a problem.
Also, remember that when you change the cost of a vertex you need to
be careful how you do it. The best way is to remove the vertex from the
priority queue, change the cost, and then put it back. The slickest way to do all of this is to store the costs in a map (mapped from Vertex objects),
use a PriorityQueue and implement a Comparator object that
uses the costs in the map to do the comparing (You then create an instance of that object and pass it into the constructor of the priority queue).
The other option is to have a new object that has both a Vertex and cost and store those in the priority queue, but that makes removing them to change the cost much more difficult.
There is a test program on the AlgorithmTests page.
Your algorithm should be as efficient as possible. You can use any resources you want to find the best algorithm to use, but you must write your own code.
Hand in your Java file using
Webhandin 385-HW3, making sure your Java class name clearly indicate which algorithm is which.
Describe your algorithm (specifying the name if it is a well known algorithm) and gives a complete complexity analysis of the algorithm.
Print out your analysis and bring it to class!.
Outputting just the tree weight will get you up to 75% credit.
Outputting the edges as well will earn you up to
87.5%.
Outputting the edges in the specified order (each edge has the vertices in increasing order and the list is also presented in increasing order) will earn you up to 100%.