任务描述 本关任务：以Prim算法获得最小生成树。 相关知识 1．掌握最小生成树的定义和构造方法； 2．掌握最小生成树的两种常用生成算法及效率分析。 测试说明 平台会对你编写的代码进行测试： 测试输入： 3 3， a b c a b 3 b c 6 a c 9 预期输出： 边 a--->b 边 b--->c

以下是使用 Prim 算法求解最小生成树的 Python 代码实现：

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):
        for i in range(1, self.V):
            print("边", parent[i], "<--->", i, "权重:", self.graph[i][parent[i]])

    def minKey(self, key, mstSet):
        min = float('inf')
        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 = [float('inf')] * 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)

其中，`Graph` 类中的 `__init__` 方法用来初始化一个图，`printMST` 方法用于打印最小生成树，`minKey` 方法用于查找未包含在最小生成树中键值最小的顶点，`primMST` 方法是 Prim 算法的核心实现。

对于测试输入数据，可以使用以下代码进行调用：

g = Graph(3)
g.graph = [[0, 3, 9],
           [3, 0, 6],
           [9, 6, 0]]

g.primMST()

输出结果为：

边 0 <---> 1 权重: 3
边 1 <---> 2 权重: 6