Finding MSTs in Edgy
About
In this session, you will learn how to find Mininum Spanning Trees in Graphs using these algorithms:
- Kruskal’s
- Prim’s
This activity will involve combining all of the Networks and Coding concepts that you have learned about in the workshop’s activities. You will also learn how to sort edges in a Graph and about Priority Queues, which are a Collection that are similar to Lists and Stacks.
Minimum Spanning Trees are mentioned in the MS-N1 Networks and Paths Course Content for the Mathematics Standard Year 12 Syllabus. The Course Content section N1.2: Shortest paths mentions that students should be able to:
- determine the Minimum Spanning Tree of a given Network with weighted edges (ACMGM101, ACMGM102)
- determine the Minimum Spanning Tree by using Kruskal’s or Prim’s algorithms or by inspection
- determine the definition of a Tree and a Minimum Spanning Tree for a given Network
We will implement both algorithms (Kruskal’s and Prim’s) today in Edgy and demonstrate how a computer can quickly find an MST on larger Graphs, where it may not be possible (or very difficult) to find an MST by inspection.
Files
Activity Solutions
The Block Images that are referred to in the Finding MSTs in Edgy Activity can be viewed on the Solutions page.
Finished Project
You can download the finished Finding MSTs in Edgy project from this link, as an XML file that can be imported into Edgy.