Я пытаюсь реализовать алгоритм Prim с Python 3, который подсчитывает общий вес генерируемого MST. И я делаю что-то необычное, используя «массив» для отслеживания непосещенных узлов.
Вот мой код:
def Prim(Graph):
# row 1 is "still in R"
# row 2 is the connector vertex
# row 3 is the cost
total = 0
A = []
n = len(Graph)
A = [[None for x in range(0, n)] for y in range(1, 4)]
#Debugging purposes
#print(A)
for x in range(1, n):
A[0][x] = 'Y'
A[1][x] = 0
A[2][x] = 0
for neighbour in Graph[1]:
A[1][neighbour-1] = 1
A[2][neighbour-1] = Graph[1][neighbour]
#Debugging purposes
#print("Neighbour: ", neighbour, "Weight: ", Graph[1][neighbour])
current = 1
T = [current]
MST_edges = {}
count = 0
while len(T) < n:
x = search_min(current, A)
T.append(x)
MST_edges[x] = A[1][x]
A[0][x] = 'N'
total += A[2][x]
#print(Graph)
#print(A)
for neighbour in Graph[x]:
#print(neighbour)
#print(A[2][neighbour-1])
if A[0][neighbour-1] != 'N':
if Graph[x][neighbour] < A[2][neighbour-1]:
A[1][neighbour-1] = x
A[2][neighbour-1] = Graph[x][neighbour]
count += 1
current = T[count]
return total
def search_min(current, A):
minimum_cost = 100
minimum_vertex = 1
for x in range(1,len(A[0])):
if A[1][x] != None and A[0][x] != 'N' and A[2][x] < minimum_cost:
minimum_cost = A[2][x]
minimum_vertex = x
#Debugging
## print("x", x)
## print("cost",minimum_cost)
## print("vertex",x)
return minimum_vertex
Иногда это дает мне смехотворно низкие веса, такие как 20 (что почти невозможно, поскольку минимальный вес всех ребер равен 10). Проблема, вероятно, в цикле while:
while len(T) < n:
x = search_min(current, A)
T.append(x)
MST_edges[x] = A[1][x]
A[0][x] = 'N'
total += A[2][x]
#print(Graph)
#print(A)
for neighbour in Graph[x]:
#print(neighbour)
#print(A[2][neighbour-1])
if A[0][neighbour-1] != 'N':
if A[2][neighbour-1] != None and Graph[x][neighbour] < A[2][neighbour-1]:
A[1][neighbour-1] = x
A[2][neighbour-1] = Graph[x][neighbour]
count += 1
current = T[count]
Но я понятия не имею, с какой стороны. Уже довольно поздно, и у меня болит голова, любой, кто мог бы помочь, был бы великолепен.
EDIT Вот пример создаваемого MST. По какой-то причине есть вершины с 0 взвешенными ребрами.
график = конструкция_граф (20) Прим (граф) {3: 0, 5: 0, 8: 0, 16: 0, 6: 5, 9: 3, 7: 8, 11: 5, 15: 11, 12: 11 , 2:8, 18:2, 19:2, 1:19, 10:19, 14:10, 17:5, 13:16, 4:1}
(Внимательно взглянув на мой код, вы увидите, что для значения x:y x — это значение вершины, а y — вес соединительного ребра. По какой-то причине есть вершины со взвешиванием 0)
return total, A
(или что-нибудь сMST_edges
). - person Blckknght   schedule 08.04.2017