用 python语言实现prim算法

Prim算法是一种用于求解加权无向连通图的最小生成树的算法。它的基本思想是从一个顶点开始，不断向外扩张，每次找到与当前生成树最近的一个未加入生成树的顶点，并将其加入生成树中，直到所有顶点都被加入为止。

以下是用python语言实现Prim算法的基本步骤：

1. 选定一个起始点，将其加入生成树中，同时将其所有邻居顶点加入候选集中。
2. 在候选集中选取与当前生成树距离最近的一个顶点，将其加入生成树中。
3. 更新候选集中每个顶点到生成树的距离。
4. 重复2-3步骤，直到所有顶点都被加入生成树为止。

以下是一个基本实现示例：

import heapq

def prim(graph, start):
    # 初始化
    visited = set()
    heap = [(0, start)]
    # 记录每个顶点到生成树的距离
    dist = {start: 0}
    # 记录生成树
    tree = {}
    
    while heap:
        # 找到距离最近的顶点
        (cost, node) = heapq.heappop(heap)
        # 如果已经被访问过了，直接跳过
        if node in visited:
            continue
        # 将顶点加入生成树中
        visited.add(node)
        if node != start:
            tree[node] = dist[node]
        # 更新候选集中每个顶点到生成树的距离
        for neighbor, weight in graph[node]:
            if neighbor not in visited and (neighbor not in dist or weight < dist[neighbor]):
                dist[neighbor] = weight
                heapq.heappush(heap, (weight, neighbor))
    
    return tree