Challenge: Maximum Spanning Trees

The goal of this challenge is to implement an algorithm that computes the weight of a maximum spanning tree of a connected, weighted, and undirected graph. A maximum spanning tree is a spanning tree with the highest possible sum of its edge weights.

There are at least two different approaches to solving this problem:

• Implementing a modified version of Kruskal’s algorithm.
• Applying our implementation of Kruskal’s algorithm while also changing the input graph and processing the output differently.

Each approach will require different insights, so thinking about both will be worthwhile.

To recap, here is our implementation of Kruskal’s algorithm once again, with a slight simplification. It will return only the weight of the minimum spanning tree, not the tree itself.