Indexerror по алгоритму Прима - PullRequest
Новая
       18

Indexerror по алгоритму Прима

0 голосов
/ 24 марта 2019

Я выполняю код алгоритма этого прима с отрицательными весами, но я получаю Indexerror: список назначения списка вне диапазона прямо здесь adjMatrix[G[i][0]][G[i][1]] = G[i][2], и я не знаю, в чем проблема. спасибо за ваше время и помощь. 

def createAdjMatrix(V, G):

  adjMatrix = []

# create N x N matrix filled with 0 edge weights between all vertices
for i in range(0, V):
  adjMatrix.append([])
  for j in range(0, V):
    adjMatrix[i].append(0)

# populate adjacency matrix with correct edge weights
for i in range(0, len(G)):
#IndexError starts right here
  adjMatrix[G[i][0]][G[i][1]] = G[i][2]
  adjMatrix[G[i][1]][G[i][0]] = G[i][2]
return adjMatrix


def prims(V, G):

# create adj matrix from graph
adjMatrix = createAdjMatrix(V, G)

# arbitrarily choose initial vertex from graph
vertex = 0

# initialize empty edges array and empty MST
MST = []
edges = []
visited = []
minEdge = [None,None,float('inf')]

# run prims algorithm until we create an MST
# that contains every vertex from the graph
while len(MST) != V-1:

  # mark this vertex as visited
  visited.append(vertex)

# add each edge to list of potential edges
for r in range(0, V):
  if adjMatrix[vertex][r] != 0:
    edges.append([vertex,r,adjMatrix[vertex][r]])

# find edge with the smallest weight to a vertex
# that has not yet been visited
for e in range(0, len(edges)):
  if edges[e][2] < minEdge[2] and edges[e][1] not in visited:
    minEdge = edges[e]

# remove min weight edge from list of edges
edges.remove(minEdge)

# push min edge to MST
MST.append(minEdge)

# start at new vertex and reset min edge
vertex = minEdge[1]
minEdge = [None,None,float('inf')]

return MST

graph = [
    [0,1,6807],
    [1,2,-8874],
    [2,3,-1055],
    [3,4,4414],
    [4,5,1728],
    [5,6,-2237],
    [6,7,-7507],
    [7,8,7990],
    [8,9,-5012],
    [9,10,7353]]
## pass the # of vertices and the graph to run prims algorithm
print (prims(11, graph))

Редактировать: это трассировка 

adjMatrix[G[i][0]][G[i][1]] = G[i][2]
IndexError: list assignment index out of range
...