用python实现prim算法的一个实列

Prim算法是一种求解最小生成树的经典算法，其基本思想是从一个点出发，每次选取与当前生成树距离最近的点加入生成树，直到所有点都被加入生成树。下面是用Python实现Prim算法的代码实例：

#定义Prim算法函数
def Prim(graph):
    nodes = list(graph.keys())
    visited = [nodes]
    unvisited = nodes[1:]
    tree = []
    while unvisited:
        min_weight = float('inf')
        for node_visited in visited:
            for node_unvisited in unvisited:
                if graph[node_visited][node_unvisited] < min_weight:
                    min_weight = graph[node_visited][node_unvisited]
                    edge = (node_visited, node_unvisited)
        tree.append(edge)
        visited.append(edge)
        unvisited.remove(edge)
    return tree

#测试代码
graph = {'A': {'B': 7, 'D': 5},
         'B': {'A': 7, 'C': 8, 'D': 9, 'E': 7},
         'C': {'B': 8, 'E': 5},
         'D': {'A': 5, 'B': 9, 'E': 15, 'F': 6},
         'E': {'B': 7, 'C': 5, 'D': 15, 'F': 8, 'G': 9},
         'F': {'D': 6, 'E': 8, 'G': 11},
         'G': {'E': 9, 'F': 11}}
tree = Prim(graph)
print(tree)

以上代码中，我们定义了一个Prim算法函数，传入一个图（用字典表示），返回一个最小生成树的边集。具体实现过程是：首先选取第一个节点作为已访问节点，将其加入已访问节点集合visited中，其余节点加入未访问节点集合unvisited中。然后在未访问节点集合中寻找与已访问节点集合中距离最近的节点，将它们之间的边加入生成树的边集中。接着将这个新加入的节点加入已访问节点集合中，并从未访问节点集合中删除。循环此过程直到未访问节点集合为空，此时返回生成树的边集即可。