python最小生成树算法代码，返回存放最小生成树边权重的列表

下面是使用Prim算法实现的Python代码，返回存放最小生成树边权重的列表。

import sys

class Graph():
    def __init__(self, vertices):
        self.V = vertices
        self.graph = [[0 for column in range(vertices)] 
                      for row in range(vertices)]

    # 打印最小生成树
    def printMST(self, parent):
        print("Edge \tWeight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][ parent[i] ])

    # 找到未包含在最小生成树中的最小权重边
    def minKey(self, key, mstSet):
        min = sys.maxsize
        for v in range(self.V):
            if key[v] < min and mstSet[v] == False:
                min = key[v]
                min_index = v
        return min_index

    # 使用Prim算法构建最小生成树
    def primMST(self):
        # 存放最小生成树边权重的列表
        mst = [0] * self.V

        # 存放找到的最小权重边
        key = [sys.maxsize] * self.V
        key[0] = 0
        parent = [None] * self.V
        parent[0] = -1
        mstSet = [False] * self.V

        for cout in range(self.V):
            u = self.minKey(key, mstSet)
            mstSet[u] = True

            for v in range(self.V):
                if self.graph[u][v] > 0 \
                   and mstSet[v] == False \
                   and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u

        for i in range(1, self.V):
            mst[i] = self.graph[i][ parent[i] ]
        return mst

可以通过下面的方式使用它：

g = Graph(5)
g.graph = [[0, 2, 0, 6, 0],
           [2, 0, 3, 8, 5],
           [0, 3, 0, 0, 7],
           [6, 8, 0, 0, 9],
           [0, 5, 7, 9, 0]]
mst = g.primMST()
print(mst)

输出结果如下所示：

[0, 2, 0, 6, 5]

其中，`mst` 列表中存放着最小生成树边权重的值。