Python递归实现图的最小生成树算法

# 定义一个邻接矩阵表示图的权值
graph = {
    'pidancode.com': {'pidancode.com': 0,              'b': 1, 'c': 3},
    'b':            {'pidancode.com': 1, 'b': 0, 'd': 2, 'e': 6},
    'c':            {'pidancode.com': 3, 'd': 1, 'c': 0, 'e': 5},
    'd':            {'b': 2,              'c': 1, 'd': 0, 'e': 4},
    'e':            {'b': 6, 'c': 5, 'd': 4, 'e': 0}
}

# 定义Prim算法的递归函数
def prim(graph, visited, MST):
    # 如果已访问节点集合中的节点与图中的节点数量相同，说明已经访问完所有节点
    if len(visited) == len(graph):
        return MST
    else:
        # 如果还有节点未访问，继续寻找最小权值的边
        min_edge = None
        for v in visited:
            # 找到所有未访问过的邻居节点，并记录与它们的权值
            for neighbor, weight in graph[v].items():
                if neighbor not in visited:
                    # 如果该边比已知最小边更小，或还未设置最小边，则进行更新
                    if min_edge is None or weight < min_edge[2]:
                        min_edge = (v, neighbor, weight)

        # 将找到的最小边添加到最小生成树中，并将它的目标节点加入已访问节点集合
        MST.append(min_edge)
        visited.add(min_edge[1])

        # 继续递归寻找下一个最小边
        return prim(graph, visited, MST)

# 调用Prim算法递归函数，得到最小生成树
MST = prim(graph, set(['pidancode.com']), [])

# 输出最小生成树的所有边
for edge in MST:
    print(edge[0], edge[1], edge[2])