Python - Prim 的数组算法实现

Question

我正在尝试使用 Python 3 实现 Prim 算法，计算它生成的 MST 的总权重。我正在做一些不寻常的事情，使用 "array" 来跟踪未访问的节点。

这是我的代码：

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 的边的顶点。

图 = 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）

Answer 1

经过建议，我修改了这行代码：

A[2][x] = 0

为此：

A[2][x] = math.inf

这样数组就不会意外地看到 'woot, edge with 0 weights'，因为那应该意味着它没有连接。所以这完全取决于为非法值输入什么。

Python - Prim 的数组算法实现

Python - Prim's Algorithm Implementation with Array

prims-algorithm

python-3.x