12-06 MST Wrapup

Key question: how do you know your code produces a minimal spanning tree? Try some of these test cases.

total weight

Write a new method in the weighted graph class to return the total weight of all of the edges given.

def total_weight(self, edges: Set[Edge]]) -> int:
    return 0

test cases

• WeightedGraph(V=5, E=7), shown above. The minimal spanning tree has weight 7.
• WeightedGraph(V=20, E=29) with minimal spanning tree of weight 347.
• WeightedGraph(V=200, E=400). The weight of the minimal spanning tree is 17467.

generic setup

This would come first in your code, but it’s the least important so it’s last on this page.

from typing import Tuple, List, Set
Vertex = int
Edge = Tuple[Vertex, Vertex]

• ←Previous
Next→