prim算法python源代码

以下是使用Python实现Prim算法的示例代码：

from queue import PriorityQueue

def prim(graph, start):
    mst = [] # 存放最小生成树的边
    visited = set([start]) # 存放已访问的点
    edges = PriorityQueue() # 存放未访问的边，按权值从小到大排序
    
    # 将与起点相连的边加入edges中
    for edge in graph[start]:
        edges.put(edge)
        
    while edges.qsize()>0:
        edge = edges.get()
        if edge[1] not in visited: # 如果该边连接的点未被访问
            visited.add(edge[1])
            mst.append(edge)
            # 将与该点相连的未访问的边加入edges中
            for e in graph[edge[1]]:
                if e[1] not in visited:
                    edges.put(e)
            
    return mst

其中，`graph`是一个字典，键为节点，值为与该节点相连的边的列表，每个边由一个元组表示，包括目标节点和权值，例如：

graph = {
    'A': [('B', 4), ('H', 8)],
    'B': [('A', 4), ('C', 8), ('H', 11)],
    'C': [('B', 8), ('D', 7), ('F', 4), ('I', 2)],
    'D': [('C', 7), ('E', 9), ('F', 14)],
    'E': [('D', 9), ('F', 10)],
    'F': [('C', 4), ('D', 14), ('E', 10), ('G', 2)],
    'G': [('F', 2), ('H', 1), ('I', 6)],
    'H': [('A', 8), ('B', 11), ('G', 1), ('I', 7)],
    'I': [('C', 2), ('G', 6), ('H', 7)]
}

而`start`则是起点节点。