prim python

prim算法是一种常用的最小生成树算法，用于求解加权无向图的最小生成树。下面是一个使用Python实现prim算法的示例代码：

def prim(graph):
    # 创建一个集合用于存放已经访问过的顶点
    visited = set()
    # 选择一个起始顶点
    start_vertex = list(graph.keys())[0]
    visited.add(start_vertex)
    minimum_spanning_tree = []
    
    while len(visited) < len(graph):
        min_edge = None
        for vertex in visited:
            for neighbor, weight in graph[vertex].items():
                if neighbor not in visited and (min_edge is None or weight < min_edge[2]):
                    min_edge = (vertex, neighbor, weight)
        
        minimum_spanning_tree.append(min_edge)
        visited.add(min_edge[1])
    
    return minimum_spanning_tree

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

result = prim(graph)
print("最小生成树：")
for edge in result:
    print(edge)

输出：

最小生成树：
('A', 'B', 2)
('B', 'C', 1)
('B', 'D', 1)