Find MST Using Kruskal’s Algorithm - 10 Points
In this assignment you will use the provided code template to find the Minimum Spanning Tree of a graph using Kruskal’s Algorithm. You will not only implement the algorithm itself, but you will also implement 3 necessary functions for the union-find abstract data type, which is used to determine whether or not adding a particular edge will create a cycle.
Restrictions
• You must complete this assignment on your own; do not share your code with anyone and do not copy code from the Internet
• You must be fully compatible with python 3.6.x
• Do not modify the structure or program-flow of this assignment in any way – only add code where directed to do so by the code comments. Do not add functions, variables, or other code constructions except where told to do so.
Template Code
The returned graph object has various functions and variables defined, but you should not need to access anything in this object directly. In the function kruskal(G), notice that a sorted list of edges is already provided for you – all you need to do is access each edge within the provided loop. Note that an edge is a tuple composed of two vertex ids.
Union-Find
This data structure is covered in the text (Dasgupta 5.1.4). You will code 3 short functions within the unionFind object as outlined in the text (the makeset functionality is already provided in the unionFind object’s constructor). Follow the instructions in the code comment.
• For find(p), you must use path compression.
• For union(u,v), you must maintain rank as well as pi.
Submission
1
