prim最小生成树算法

以下是Prim算法的步骤：
1. 从图中任意选取一个顶点作为起点，将其加入生成树中。
2. 找到与生成树相邻的权值最小的边所连接的顶点，将其加入生成树中。
3. 重复第二步，直到生成树中包含了所有的顶点。

具体实现步骤如下：
1. 初始化一个空的生成树和一个包含所有顶点的未访问顶点集合。
2. 随机选择一个起始顶点，并将其加入生成树中，从未访问顶点集合中删除该顶点。
3. 遍历生成树中的所有顶点，对于每个顶点，找到与之相邻的未访问顶点中权值最小的边所连接的顶点，并将其加入生成树中，从未访问顶点集合中删除该顶点。
4. 重复第三步，直到未访问顶点集合为空。

以下是Python实现Prim算法的代码：

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()