Homework 3

Finding All MSTs

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

Task

• Create a class MSTLastname (e.g., MSTChoi) that implements the MSTAll interface.
• Override the getMinimumSpanningTrees method in MSTLastname.
• Pick either Prim's or Kruskal's algorithm for finding minimum spanning trees.
• @param graph an undirected graph containing zero to many spanning trees.
• @return list of all minimum spanning trees.
• Use the SpanningTree, Graph, Edge classes without modifying.
• Write a report that explains your logic of generating all minimum spanning trees and save it as hw3.pdf.
• Compress MSTLastname and hw3.pdf into hw3.zip and submit it to canvas: https://canvas.emory.edu/courses/32845/assignments/85381

Extra Credit

• Create an interesting graph and submit both the source code (as in MSTAllTest) and the diagram representing your graph (up to 1 point).
• Submit two codes, one finding all minimum spanning trees using Prim's algorithm and the other using Kruskal's algorithm (up to 2 point).
• Compress all source codes and necessary files to hw3-ex.zip and submit it to canvas:

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}.