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

Prime算法是解决最小生成树问题的常见算法之一，它的基本思想是从一个起始点开始，依次选择与当前生成树相邻的边中权值最小的边，将其加入生成树中，直至生成树包含所有点为止。具体步骤如下：

1. 选择一个起始点作为生成树的根节点，初始化生成树为空。

2. 将起始点的所有相邻边加入一个优先队列中，按照权值从小到大排序。

3. 从优先队列中取出权值最小的边，若该边的终点已经在生成树中，则跳过该边，继续从队列中取下一条边；否则将该边加入生成树中，并将该边的终点作为新的节点加入优先队列中。

4. 重复步骤3，直到生成树包含所有点为止。

下面是使用Python实现Prime算法生成最小生成树的代码示例：

import heapq

def prim(graph):
    n = len(graph)
    visited = [False] * n
    mst = []
    heap = [(0, 0)]
    while heap:
        cost, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        mst.append((cost, u))
        for v, w in graph[u]:
            if not visited[v]:
                heapq.heappush(heap, (w, v))
    return mst

其中，graph是一个邻接表表示的无向图，每个元素graph[u]表示节点u的所有相邻边，每个相邻边是一个二元组(v, w)，表示从节点u到节点v的一条边，权值为w。

使用该函数，可以得到图的最小生成树，输出结果为一个二元组列表，每个二元组表示一条边，第一个元素为边的权值，第二个元素为边的终点。