生成树的定义

生成树是一个连通图的一种特殊形式，它是该图的一个子图，包含了图中的所有顶点，并且是一个树（无环连通图）。生成树的边数比图的顶点数少1，保持了图的连通性。

以下是一个使用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 min_key(self, key, mst_set):
        min_value = sys.maxsize
        min_index = -1
        for v in range(self.V):
            if key[v] < min_value and mst_set[v] == False:
                min_value = key[v]
                min_index = v
        return min_index
        
    def prim_mst(self):
        key = [sys.maxsize] * self.V
        parent = [None] * self.V
        key[0] = 0
        mst_set = [False] * self.V
        
        parent[0] = -1
        
        for cout in range(self.V):
            u = self.min_key(key, mst_set)
            mst_set[u] = True
            
            for v in range(self.V):
                if self.graph[u][v] > 0 and mst_set[v] == False and key[v] > self.graph[u][v]:
                    key[v] = self.graph[u][v]
                    parent[v] = u
        
        print("Edge \tWeight")
        for i in range(1, self.V):
            print(parent[i], "-", i, "\t", self.graph[i][parent[i]])

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

以上代码使用邻接矩阵表示图，通过Prim算法生成最小生成树。输出结果是生成树的边和权重。