prim的Python实现

以下是Prim算法的Python实现[^2]：

import heapq

def prim(graph, start):
    # 初始化距离和父节点字典
    distances = {node: float('inf') for node in graph}
    parents = {node: None for node in graph}
    
    # 将起始节点的距离设为0
    distances[start] = 0
    
    # 创建一个优先队列，用于选择最小距离的节点
    pq = [(0, start)]
    
    while pq:
        # 从优先队列中选择最小距离的节点
        current_distance, current_node = heapq.heappop(pq)
        
        # 如果当前节点已经被访问过，则跳过
        if current_distance > distances[current_node]:
            continue
        
        # 遍历当前节点的邻居节点
        for neighbor, weight in graph[current_node].items():
            distance = weight
            
            # 如果找到了更短的路径，则更新距离和父节点
            if distance < distances[neighbor]:
                distances[neighbor] = distance
                parents[neighbor] = current_node
                
                # 将邻居节点加入优先队列
                heapq.heappush(pq, (distance, neighbor))
    
    # 构建最小生成树
    min_spanning_tree = {node: [] for node in graph}
    for node in parents:
        if parents[node] is not None:
            min_spanning_tree[parents[node]].append(node)
    
    return min_spanning_tree

使用这个函数，你可以传入一个图和起始节点来运行Prim算法。它将返回一个最小生成树的字典，其中键是节点，值是与该节点相连的节点列表。