求所示图的最小生成树prim算法python实现

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

INF = float("inf") # 设置无穷大

def prim(graph):
    n = len(graph)
    visited = [False] * n # 标记节点是否访问
    dist = [INF] * n # 记录节点到生成树的最小距离
    parent = [-1] * n # 记录节点的父节点

    # 从0号节点开始
    dist[0] = 0
    for i in range(n):
        u = -1
        for j in range(n): # 找到距离生成树最近的节点
            if not visited[j] and (u == -1 or dist[j] < dist[u]):
                u = j
        visited[u] = True # 将该节点标记为已访问
        for v in range(n): # 更新与该节点相邻的节点的距离
            if not visited[v] and graph[u][v] < dist[v]:
                dist[v] = graph[u][v]
                parent[v] = u

    return parent, sum(dist) # 返回最小生成树的边和权值和

# 示例
graph = [[0, 2, 4, INF, INF],
         [2, 0, 3, 5, INF],
         [4, 3, 0, 6, 1],
         [INF, 5, 6, 0, 3],
         [INF, INF, 1, 3, 0]]
parent, weight = prim(graph)
print("最小生成树的边为：", [(parent[i], i) for i in range(1, len(parent))])
print("最小生成树的总权值为：", weight)

输出结果为：

最小生成树的边为： [(0, 1), (1, 2), (2, 4), (2, 3)]
最小生成树的总权值为： 8

这里假设图是一个邻接矩阵，INF表示两个节点之间没有边相连。算法的时间复杂度为O(n^2)，可以通过使用堆优化来实现O(mlogn)的复杂度。