用python语言Prim算法编写程序实现连通无向图的最小生成树，并测试

好的，下面是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

    def primMST(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V 
        key[0] = 0 
        mstSet = [False] * self.V

        parent[0] = -1 

        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

        self.printMST(parent)

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]]

g.primMST()

上面的代码实现了Prim算法，用于求解连通无向图的最小生成树。测试用例是一个5个顶点的无向图，其边权如下：

  2     3
0---1---2
|\  |  /|
| \ | / |
6  8 7  9
| / | \ |
|/  |  \|
3   5   7

输出结果是：

Edge    Weight
0 - 1   2
1 - 2   3
0 - 3   6
1 - 4   5

这是最小生成树的边集合，其总权重为16。