Python - 用数组执行Prim的算法

我正在试图用Python 3实现Prim的算法，它计算它生成的MST的总权重。我正在做一些不寻常的事情，用一个“数组”来跟踪未访问的节点。Python - 用数组执行Prim的算法

这里是我的代码：

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]

但我不知道什么部分。越来越迟，我的头痛，任何能够帮助的人都会很棒。

编辑下面是它生成的MST的一个例子。由于某些原因，存在具有0加权边的顶点。

graph = construct_graph（20） Prim（图）{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）

来源

2017-04-08 RosaryLightning X

你可以举一个图表的例子来计算错误的权重吗？也许你应该让函数返回它找到的树，而不仅仅是重量，这样你就可以看到它出错了（这可能会告诉你它在哪里犯错）。尝试'返回总数，A'（或者用'MST_edges'）。 – Blckknght

@Blckknght嗨，感谢您的建议，我添加了它生成的MST的一个例子 –

在建议之后，我改变了这个代码行：

A[2][x] = 0

要这样：

A[2][x] = math.inf

这是为了让数组不小心看到“0的权重活泉，边缘”因为这应该意味着它没有连接。所以这是非常重要的。

来源

2017-04-08 17:21:07

Python - 用数组执行Prim的算法

回答

相关问题