> For the complete documentation index, see [llms.txt](https://emory.gitbook.io/dsa-java/llms.txt). Markdown versions of documentation pages are available by appending `.md` to page URLs; this page is available as [Markdown](https://emory.gitbook.io/dsa-java/minimum-spanning-trees/homework.md).

# 8.6. Homework

## 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`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/graph/span/MSTAllHW.java)  that inherits the [`MSTAll`](https://github.com/emory-courses/dsa-java/blob/master/src/main/java/edu/emory/cs/graph/span/MSTAll.java) interface.
* Override the `getMinimumSpanningTrees()` method.
* Feel free to use any classes in the [graph](https://github.com/emory-courses/dsa-java/tree/master/src/main/java/edu/emory/cs/graph) package without modifying.
* Write a report that explains the logic and worst-case complexity of your program and save it as `hw3.pdf`.

{% hint style="info" %}
You may want to start with the implementation of either [Prim's](/dsa-java/minimum-spanning-trees/prims-algorithm.md) or [Kruskal's](/dsa-java/minimum-spanning-trees/kruskals-algorithm.md) algorithm and update the code to find all minimum spanning trees.
{% endhint %}

## Extra Credit

* Create an interesting graph and submit both the source code (as in [`MSTAllHWTest`](https://github.com/emory-courses/dsa-java/blob/master/src/test/java/edu/emory/cs/graph/span/MSTAllHWTest.java)) 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`}.

&#x20;