class MinimumSpanningTree(object):
def __init__(self, v):
self.v = v
self.e = 0
self.mincost = [float("inf") for i in range(v)]
self.cost = [[float("inf") for i in range(v)] for i in range(v)]
self.used = [0 for i in range(v)]
def append(self, _from, _to, _cost):
self.cost[_from][_to] = _cost
self.e += 1
def prim(self):
res = 0
self.mincost = [float("inf") for i in range(v)]
self.used = [0 for i in range(v)]
self.mincost[0] = 0
while 1:
v = -1
for u in range(self.v):
if not self.used[u] and (v == -1 or self.mincost[u] < self.mincost[v]):
v = u
if v == -1:
break
self.used[v] = 1
res += self.mincost[v]
for u in range(self.v):
self.mincost[u] = min(self.mincost[u], self.cost[v][u])
return res
def append_test(self):
self.append(0, 2, 1)
self.append(1, 2, 2)
self.append(1, 4, 10)
self.append(2, 0, 1)
self.append(2, 1, 2)
self.append(2, 3, 3)
self.append(2, 5, 7)
self.append(3, 2, 3)
self.append(3, 5, 1)
self.append(3, 6, 5)
self.append(4, 1, 10)
self.append(4, 5, 5)
self.append(5, 2, 7)
self.append(5, 3, 1)
self.append(5, 4, 4)
self.append(5, 6, 8)
self.append(6, 3, 5)
self.append(6, 5, 8)
