def kruskal_mst(graph):
edges_accepted = <NUM_LIT:0><EOL>ds = DisjointSet()<EOL>pq = PriorityQueue()<EOL>accepted_edges = []<EOL>label_lookup = {}<EOL>nodes = graph.get_all_node_ids()<EOL>num_vertices = len(nodes)<EOL>for n in nodes:<EOL><INDENT>label = ds.add_set()<EOL>label_lookup[n] = label<EOL><DEDENT>edges = graph.get_all_edge_objects()<EOL>for e in edges:<EOL><INDENT>pq.put(e['<STR_LIT:id>'], e['<STR_LIT>'])<EOL><DEDENT>while edges_accepted < (num_vertices - <NUM_LIT:1>):<EOL><INDENT>edge_id = pq.get()<EOL>edge = graph.get_edge(edge_id)<EOL>node_a, node_b = edge['<STR_LIT>']<EOL>label_a = label_lookup[node_a]<EOL>label_b = label_lookup[node_b]<EOL>a_set = ds.find(label_a)<EOL>b_set = ds.find(label_b)<EOL>if a_set != b_set:<EOL><INDENT>edges_accepted += <NUM_LIT:1><EOL>accepted_edges.append(edge_id)<EOL>ds.union(a_set, b_set)<EOL><DEDENT><DEDENT>return accepted_edges<EOL>
Implements Kruskal's Algorithm for finding minimum spanning trees.
    Assumes a non-empty, connected graph.