Prim's Algorithm

import heapqdefprims(graph, start_node): mst = [] visited = set([start_node]) edges = [ (weight, start_node, to_node)for to_node, weight in graph[start_node].items() ] heapq.heapify(edges) total_weight = 0while edges: weight, from_node, to_node = heapq.heappop(edges)if to_node not in visited: visited.add(to_node) mst.append((from_node, to_node, weight)) total_weight += weightfor next_node, next_weight in graph[to_node].items():if next_node not in visited: heapq.heappush(edges, (next_weight, to_node, next_node))return mst, total_weight