最小生成树python模板

最小生成树（Minimum Spanning Tree，简称MST）是一种在连通图中找到最小权重生成树的算法。下面是一个使用Prim算法实现最小生成树的Python模板：

import sys

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

    def printMST(self, parent):
        print("边\t权重")
        for i in range(1, self.V):
            print(f"{parent[i]} - {i}\t{self.graph[i][parent[i]]}")

    def minKey(self, key, mstSet):
        min_val = sys.maxsize
        min_index = -1
        for v in range(self.V):
            if key[v] < min_val and not mstSet[v]:
                min_val = key[v]
                min_index = v
        return min_index

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

        parent = -1

        for _ 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 not mstSet[v]
                    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算法来实现最小生成树。首先，我们定义了一个Graph类，其中包含了图的顶点数和邻接矩阵。`primMST`方法是Prim算法的实现，它通过选择权重最小的边来构建最小生成树。`minKey`方法用于找到当前权重最小的顶点。`printMST`方法用于打印最小生成树的边和权重。