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))