Python算法

01  def prim(graph,start):01      vertex_list = ["A","B","C","D","E","F"] #顶点列表02      tree_vertex_list = []                       #最小生成树顶点列表03      tree_vertex_list.append(start)              #最小生成树第一个顶点04      closest = []                                #最小生成树顶点索引列表05      lowcost = []                                #最小生成树各顶点与其他顶点的距离06      n = len(vertex_list)                        #图的顶点个数07      index = vertex_list.index(start)            #起始点的索引08      for i in range(0,n):09          lowcost.append(graph[index][i])         #初始化lowcost列表10          closest.append(index)                   #初始化closest列表11      for i in range(1,n):                        #插入n-1个顶点12          k = 013          min = maxValue14          for j in range(0,n):15              if(lowcost[j]!=0 and lowcost[j]<min):16                  min = lowcost[j]        #获取插入最小生成树的权重最小顶点的权重17                  k = j                   #获取插入最小生成树的权重最小顶点的索引18          tree_vertex_list.append(vertex_list[k]) #加入最小生成树顶点列表19          lowcost[k] = 0                          #最小生成树到该顶点距离20          for j in range(0,n):21              if(lowcost[j]!=0 and graph[k][j]<lowcost[j]):22                  lowcost[j] = graph[k][j]        #更新插入顶点后的lowcost列表23                  closest[j] = k                  #更新插入顶点后的closest列表

01 maxValue = float("inf")                         #设置最大值为无穷大02 graph = [[0,9,maxValue,maxValue,maxValue,8,5],    #图的权重列表03          [9,0,6,maxValue,maxValue,maxValue,maxValue],04          [maxValue,6,0,7,maxValue,maxValue,maxValue],05          [maxValue,maxValue,7,0,13,maxValue,10],06          [maxValue,maxValue,maxValue,13,0,12,15],07          [8,maxValue,maxValue,maxValue,12,0,maxValue],08          [5,maxValue,maxValue,10,15,maxValue,0]]09 def prim(graph,start):10     vertex_list = ["A","B","C","D","E","F","G"] #顶点列表11     tree_vertex_list = []                       #最小生成树顶点列表12     tree_vertex_list.append(start)              #最小生成树第一个顶点13     closest = []                                #最小生成树顶点索引列表14     lowcost = []                                #最小生成树各顶点与其他顶点的距离15     n = len(vertex_list)                        #图的顶点个数16     index = vertex_list.index(start)            #起始点的索引17     for i in range(0,n):18         lowcost.append(graph[index][i])         #初始化lowcost列表19         closest.append(index)                   #初始化closest列表20     for i in range(1,n):                        #插入n-1个顶点21         k = 022         min = maxValue23         for j in range(0,n):24             if(lowcost[j]!=0 and lowcost[j]<min):25                 min = lowcost[j]        #获取插入最小生成树的权重最小顶点的权重26                 k = j                   #获取插入最小生成树的权重最小顶点的索引27         tree_vertex_list.append(vertex_list[k]) #加入最小生成树顶点列表28         print(vertex_list[closest[k]]+'—'+vertex_list[k]+'权重：'+str(lowcost[k]))#打印边的权重29         lowcost[k] = 0                          #最小生成树到该顶点距离30         for j in range(0,n):31             if(lowcost[j]!=0 and graph[k][j]<lowcost[j]):32                 lowcost[j] = graph[k][j]        #更新插入顶点后的lowcost列表33                 closest[j] = k                  #更新插入顶点后的closest列表34     print("最小生成树顶点："+str(tree_vertex_list)) #打印最小生成树各顶点35 prim(graph,"A")                                     #调用函数并设置起始顶点为A                               #调用函数并设置起始顶点为A