prim算法实现最小生成树的python代码

以下是使用Prim算法实现最小生成树的Python代码：

import sys

def prim(graph, start):
    # 初始化距离和父节点字典
    dist = {}
    parent = {}
    for vertex in graph:
        dist[vertex] = sys.maxsize
        parent[vertex] = None
    
    # 将起始节点的距离设为0
    dist[start] = 0
    
    # 选择最小权重的节点
    while graph:
        min_vertex = None
        for vertex in graph:
            if min_vertex is None:
                min_vertex = vertex
            elif dist[vertex] < dist[min_vertex]:
                min_vertex = vertex
        
        # 更新距离和父节点
        for neighbor, weight in graph[min_vertex].items():
            if neighbor in graph and weight < dist[neighbor]:
                dist[neighbor] = weight
                parent[neighbor] = min_vertex
        
        # 移除已经访问过的节点
        del graph[min_vertex]
    
    return parent

# 测试代码
graph = {
    'A': {'B': 2, 'C': 3},
    'B': {'A': 2, 'C': 1, 'D': 1},
    'C': {'A': 3, 'B': 1, 'D': 2},
    'D': {'B': 1, 'C': 2}
}

start_vertex = 'A'
parent = prim(graph, start_vertex)

# 输出最小生成树的边
for vertex, parent_vertex in parent.items():
    if parent_vertex is not None:
        print(f"Edge: {parent_vertex} - {vertex}")