1) Windows 10
2) Python 3.8.3
Есть код алгоритма, но при вводе нужного графа он выдает 3 ошибки, как заставить код работать с этим графом?
2) Python 3.8.3
Код:
class Graph:
def __init__(self, vertices):
self.V = vertices
self.graph = []
def addEdge(self, u, v, w):
self.graph.append([u, v, w])
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] > rank[yroot]:
parent[xroot] = yroot
elif rank[yroot] > rank[xroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def MST(self):
parent = []
rank = []
cheapest = []
numTrees = self.V
MSTweight = 0
for node in range(self.V):
parent.append(node)
rank.append(0)
cheapest = [-1] * self.V #меньше -1 не весят компоненты
while numTrees > 1:
for i in range(len(self.graph)):
u, v, w = self.graph[i]
set1 = self.find(parent, u)
set2 = self.find(parent, v)
if set1 != set2:
if cheapest[set1] == -1 or cheapest[set1][2] > w:
cheapest[set1] = [u, v, w]
if cheapest[set2] == -1 or cheapest[set2][2] > w:
cheapest[set2] = [u, v, w]
for node in range(self.V):
if cheapest[node] != -1:
u, v, w = cheapest[node]
set1 = self.find(parent, u)
set2 = self.find(parent, v)
if set1 != set2: #кандидат проходит
MSTweight += w
self.union(parent, rank, set1, set2)
print("Дуга %d-%d с весом %d включена в остов" % (u, v, w))
numTrees -= 1
cheapest = [-1] * self.V
print("Вес минимального остова равен ", MSTweight)
if __name__ == '__main__':
g = Graph(6)
g.addEdge(1, 2, 6)
g.addEdge(1, 3, 1)
g.addEdge(1, 4, 5)
g.addEdge(2, 3, 5)
g.addEdge(2, 5, 3)
g.addEdge(3, 5, 6)
g.addEdge(3, 6, 4)
g.addEdge(5, 6, 5)
g.addEdge(4, 6, 2)
g.MST()