import mathnodes = ['A','B','C','D','E','F'] # 结点数组vecs = [[0,1,6],[0,2,1],[0,3,5],[1,0,6],[1,2,5],[1,4,3],[2,0,1],[2,1,5],[2,3,5],[2,4,6],[2,5,4],[3,0,5],[3,2,5],[3,5,2],[4,1,3],[4,2,6],[4,5,6],[5,2,4],[5,3,2],[5,4,6]] # 边[i,j,value]数组def Prim(nodes,vecs):n = len(nodes) # 结点个数adjMat = [[math.inf]*n for i in range(n)] # 邻接矩阵for vec in vecs: # 创造邻接矩阵adjMat[vec[0]][vec[1]] = vec[2]print('邻接矩阵展示:')for i in range(n):for j in range(n):print('{:3d}'.format(adjMat[i][j]) if adjMat[i][j] != math.inf else '{:3s}'.format('inf'),end = ' ') print()d = [0] # 辅助数组，实时记录"最小生成树"外的所有结点到"最小生成树"的最短距离d.extend([math.inf]*(n-1))vis = [1] # 辅助数组，实时标记"最小生成树"外的所有结点vis.extend([0]*(n-1))pre = [-1]*n # 辅助数组，实时记录"最小生成树"外的所有结点到"最小生成树"最短距离的前驱结点j = 0 # 新加入"最小生成树"的结点Sum = 0 # "最小生成树"路径总长度print('Prim算法的最小生成树:')for i in range(n-1): # 依次产生最小生成树的n-1条边Min = math.infk = -1for t in range(1,n):if not vis[t] and adjMat[t][j] < d[t]: # 通过新加入"最小生成树"的结点，更改距离数组d[t] = adjMat[t][j]pre[t] = jif not vis[t] and d[t] < Min: # 比较出"最小生成树"之外的结点中到"最小生成树"最近的结点Min = d[t]k = tprint(nodes[pre[k]],'------->',nodes[k])Sum += d[k]vis[k] = 1 # 将其加入"最小生成树"j = kprint('Prim算法带权路径总长度:')print(Sum)Prim(nodes,vecs)
输出:
邻接矩阵展示:
inf 6 1 5 inf inf
6 inf 5 inf 3 inf
1 5 inf 5 6 4
5 inf 5 inf inf 2
inf 3 6 inf inf 6
inf inf 4 2 6 inf
Prim算法的最小生成树:
A -------> C
C -------> F
F -------> D
C -------> B
B -------> E
Prim算法带权路径总长度:
15
