prim算法求最小生成树

Prim算法是一种用于求解加权无向图的最小生成树的贪心算法。其基本思想是从任意一个顶点开始，不断选择与当前生成树距离最短的未访问顶点加入生成树中，直到所有顶点都被访问。

具体实现步骤如下：

1. 从任意一个顶点开始，将其加入生成树中。

2. 对于当前已加入生成树的所有顶点，选择与其距离最短的未访问顶点，将其加入生成树中。

3. 重复步骤2，直到所有顶点都被访问。

代码实现如下（假设图用邻接矩阵表示）：

def prim(graph):
    n = len(graph)
    # 初始化生成树
    tree = [0] * n
    # 初始化距离数组
    dist = [float('inf')] * n
    # 随便选一个顶点作为起点
    dist[0] = 0
    # 遍历所有顶点
    for i in range(n):
        # 找到距离最近的未访问顶点
        u = -1
        min_dist = float('inf')
        for j in range(n):
            if not tree[j] and dist[j] < min_dist:
                u = j
                min_dist = dist[j]
        # 将该顶点加入生成树中
        tree[u] = 1
        # 更新距离数组
        for v in range(n):
            if not tree[v] and graph[u][v] < dist[v]:
                dist[v] = graph[u][v]
    return tree

其中，graph是邻接矩阵，tree表示生成树，dist表示距离数组。