8.6. Homework

This section describes the homework assignment to develop an algorithm to find all minimum spanning tress given an undirected graph.

Finding All Minimum Spanning Trees

Your task is to write a program that finds all minimum spanning trees given an undirected graph.

Tasks

• Create a class called MSTAllHW that inherits the MSTAll interface.

• Override the getMinimumSpanningTrees() method.

• Feel free to use any classes in the graph package without modifying.

• Write a report that explains the logic and worst-case complexity of your program and save it as hw3.pdf.

You may want to start with the implementation of either Prim's or Kruskal's algorithm and update the code to find all minimum spanning trees.

Extra Credit

• Create an interesting graph and submit both the source code (as in MSTAllHWTest) and the diagram representing your graph (up to 1 point).

Notes

• Test your code with graphs consisting of zero to many spanning trees.

• Your output must include only minimum spanning trees.

• Your output should not include redundant trees. For example, if there are three vertices, 0, 1, and 2, {0 -> 1, 0 -> 2} is considered the same as {0 -> 1, 0 <- 2} or {0 <- 1, 0 -> 2} or {0 <-1, 0 <- 2}.