prim算法python

以下是Python实现的Prim算法：

# 通过prim算法生成最小生成树
def prim(graph, start):
    # 用于保存生成树的边
    tree = []
    # 用于保存已经在生成树中的节点
    visited = [start]
    # 获取节点个数
    nodes = len(graph)
    # 循环nodes-1次，每次选出一个节点加入生成树中
    for i in range(nodes - 1):
        # 用于保存生成树中所有节点到非生成树节点的最小边
        min_edge = [None, None, float('inf')]
        # 遍历所有在生成树中的节点
        for u in visited:
            # 遍历与当前节点相连的所有边
            for v, w in graph[u]:
                # 如果该节点不在生成树中，则比较该边是否为最小边
                if v not in visited and w < min_edge[2]:
                    min_edge = [u, v, w]
        # 将最小边加入生成树中
        tree.append(min_edge)
        # 将该边连接的节点加入生成树中
        visited.append(min_edge[1])
    return tree

其中，`graph`是一个字典，键表示节点，对应的值是一个列表，列表中存储与该节点相连的边，每个边是一个二元组，第一个元素是连接的节点，第二个元素是边的权重。`start`表示从哪个节点开始生成最小生成树。该算法的时间复杂度为O(ElogV)，其中E为边数，V为节点数。