def prim(g): # dist keeps track of each node's distance to the MST dist = [99999] * len(g) # arbitrarily large for infinity intree = [False] * len(g) # no nodes in tree yet treecost = 0 dist[0] = 0 # set any node's distance to zero for i in range(len(g)): # Find node with minimum distance node = -1 for i in range(len(dist)): if not intree[i] and (node == -1 or dist[i] < dist[node]): node = i treecost += dist[node] intree[node] = True # Update dist for neighbors of the just-added node for e in g[node]: if e[1] < dist[e[0]]: dist[e[0]] = e[1] return treecost # Graph in adjacency list form: # Each inner list represents the collection of edges attached to the node # An edge pair (n,w) represents n, the other node, and w, the weight # Nodes are represented by their index in the list graph = [[(2,5), (3,8)], [(3,3), (4,6), (5,2)], [(0,5), (3,2), (4,3)], [(0,8), (1,3), (2,2), (5,7)], [(1,6), (2,3)], [(1,2), (3,7)]] print(prim(graph))