# PrimMST(G, s): # foreach (Vertex v : G): # d[v] = +inf # p[v] = NULL # d[s] = 0 # PriorityQueue Q // min distance, defined by d[v] # Q.buildHeap(G.vertices())
# Graph T // "labeled set"
# repeat n times: # Vertex m = Q.removeMin() # T.add(m) # foreach (Vertex v : neighbors of m not in T): # if cost(v, m) < d[v]: # d[v] = cost(v, m) # p[v] = m
defprim(graph, root):
# Input: G, Graph; # s, vertex in G, starting vertex # Output: T, a minimum spanning tree (MST) of G
prev = None path = [] total = 0# Total cost of edges in tree visited = set() # Set of vertices in tree Node = namedtuple("Node",("v","weight")) heap = MyHeap() # Unexplored edges ordered by cost heap.push(Node(root,0)) whilenot heap.empty(): cur_node = heap.pop() if cur_node.v notin visited: visited.add(cur_node.v) total += cur_node.weight if prev: path.append((prev,cur_node.v,cur_node.weight)) prev = cur_node.v for neighbour in graph[cur_node.v]: if neighbour notin visited: heap.push(Node(neighbour, graph[cur_node.v][neighbour]))