def kruskals(graph, edges):

Your code must be in a file called kruskals.py. Your algorithm must be in a function called Kruskals. Starter code is attached to this assignment. Your kruskals function will take two arguments: an adjacency list representation of a undirected, weighted graph and an edge weight dictionary mapping node tuples (edges) to integers (edge weights). Your code should not modify any of the arguments that are passed to it (i.e. it shouldn't mutate the original graph objects). Your function should return the total weight (i.e. the sum of all the edge weights) of a minimum spanning tree in the graph. If the graph has no edges, the total weight of the MST is 0. Your algorithm must use a disjoint-set data structure to check if adding an edge to the current spanning tree will introduce a cycle. You may implement this any way you like (as long as your data structure is fundamentally a disjoint- set), but the most efficient and interesting implementation is with a rooted tree that uses path compression and union by rank. Graph representation Graphs will be represented as dictionaries where each key is a node label and each value is a list of labels, representing the node's edges. For example, the dictionary entry 'a': ['b', 'c'] means the node with label a has two edges: one to b, and one to c. Labels may be strings, integers, etc. Because the graph is undirected, if node u has an edge to v, then v will be in u's adjacency list and u will be in v's adjacency list. Edge weights will be represented as dictionaries where each key is a tuple of node labels and each value is an integer weight. For example, the dictionary entry ('c', 'b'): 7 means the edge between b and c has weight 7. Each undirected edge will be represented exactly once in the edge weight dictionary, in arbitrary order. For example, if b has an edge to c, then the edge weight dictionary will either contain the tuple ('b', 'c') or the tuple ('c', 'b'), but not both. You may implement your disjoint-set any way you like, as long as fundamentally, your implementation maintains disjoint (i.e. non-overlapping) collections of connected nodes that are merged when an edge connecting them is added to the minimum spanning tree. List implementation The easiest way to implement a disjoint-set is to maintain a dictionary mapping representative elements to lists of nodes. Two nodes are in the same set if they're both in the list associated with the same representative element. To merge sets with representative elements u and v, you can append us list of nodes to vs list of nodes and delete us entry in the dictionary, since its set has now been merged into vs set. This implementation is simple but inefficient, as finding the representative element for a given node may require iterating over the entire list of nodes for every representative element, which is O(N). Here's an example of how your kruskals function should work: = graph { "a": ["b", "c", "d"], "b": ["a", "c", "f"], "C": ["a", "b", "d", "e"], "d": ["a", "c", "e"], "e": ["c", "d", "f"], "f": ["b", "e", "g"], "g": ["f"], } = edges { ("a", "b"): 1, ("a", "c"): 7, ("a", "d"): 3, ("b", "c"): 2, ("f", "b"): 6, ("c", "d"): 1, ("c", "e"): 8, ("d", "e"): 4, ("e", "f"): 1, ("f", "g"): 3, } mst_weight kruskals(graph, edges) print(mst_weight) # prints 12, total weight of MST found