使用prime算法生成最小生成树

Prime算法是一种贪心算法，用于生成最小生成树。它的基本思想是从一个起点开始，每次加入一个距离已有点集最近的点，直到所有点都被加入为止。

具体实现过程如下：

1. 初始化一个空的集合S，将起点加入其中。
2. 从剩余的点中选择一个距离S中的点集最近的点，将其加入到S中。
3. 更新其他点到S的距离，如果有更短的路径，则更新距离。
4. 重复步骤2和3，直到所有点都被加入到S中。

以下是一个使用Prime算法生成最小生成树的示例代码，假设图的边权值存储在邻接矩阵中：

def prim(graph):
    n = len(graph)
    INF = float('inf')
    dist = [INF] * n # 存储每个点到S的距离
    visited = [False] * n # 标记每个点是否已经加入S
    parent = [-1] * n # 存储每个点的父节点
    dist[0] = 0 # 从第一个点开始生成最小生成树

    for i in range(n):
        # 找到距离S最近的点
        u = -1
        for j in range(n):
            if not visited[j] and (u == -1 or dist[j] < dist[u]):
                u = j
        visited[u] = True

        # 更新其他点到S的距离
        for v in range(n):
            if not visited[v] and graph[u][v] < dist[v]:
                dist[v] = graph[u][v]
                parent[v] = u

    # 构造最小生成树
    tree = []
    for i in range(1, n):
        tree.append((parent[i], i))

    return tree

这个算法的时间复杂度为O(n^2)，如果使用堆优化可以优化到O(mlogn)，其中m为边数。