利用prim算法求最小生成树

Prim算法是一种用于求解最小生成树的贪心算法。它的基本思想是从一个点开始，每次选择与当前生成树相邻的最小边，直到生成树包含所有节点为止。具体实现可以使用优先队列来维护当前生成树与未加入生成树的节点之间的最小边。

以下是Prim算法的伪代码：

1. 选取任意一个节点作为起点，将其加入生成树中。
2. 将起点与其它节点之间的边加入优先队列中。
3. 从优先队列中取出一条权值最小的边，如果该边连接的节点未被加入生成树，则将该节点加入生成树中，并将该节点与其它未加入生成树的节点之间的边加入优先队列中。
4. 重复步骤3，直到生成树包含所有节点。

以下是Prim算法的Python实现：

import heapq

def prim(graph):
    n = len(graph)
    visited = [False] * n
    heap = [(0, 0)]  # (权值, 节点编号)
    mst = []
    while heap:
        w, u = heapq.heappop(heap)
        if visited[u]:
            continue
        visited[u] = True
        mst.append((w, u))
        for v, weight in graph[u]:
            if not visited[v]:
                heapq.heappush(heap, (weight, v))
    return mst

其中，graph是一个邻接表表示的图，每个元素是一个列表，表示与该节点相邻的节点及其边权。