- Tell students the story of the Muddy City, where the roads get too muddy to use when it rains. The mayor wants to spend the minimum amount of money necessary paving streets such that everyone can travel from their house to anyone else’s house using only paved roads.
- Each street is made up of a certain number of stones. The number of stones represents the cost of paving that street.
- Tell students this is the Muddy City Problem.
- Explain to students that problems like these are called minimal spanning tree problems.
- Explain to students that problems like these are called minimal spanning tree problems.
- Check out the CS Unplugged Minimal Spanning Trees Activity for more details.
- Note from CS Teaching Tips Team: A spanning tree connects all the vertices of a connected, undirected graph. A minimal spanning tree’s connections have the smallest total weight of all possible spanning trees.
- Check out this Wikipedia entry on minimum spanning trees for more information.
- Note from CS Teaching Tips Team: A spanning tree connects all the vertices of a connected, undirected graph. A minimal spanning tree’s connections have the smallest total weight of all possible spanning trees.
- Learn how to incorporate this into your curriculum by visiting ECS Curriculum Version 5.0 and navigating to Day 17 in Unit 2 (page 96).