問題：要用Prim算法求最小生成樹，得有一個帶權連通圖，求問如何用這段碼創建如下圖的帶權連通圖
利用以下代碼創建
import copyfrom typing import ListMAXV = 10 # 最多頂點個數INF = 0x3f3f3f3f # (十六進制)表示∞# 設計鄰接矩陣類class MatGraph: def __init__(self, n=0, e=0): self.edges = [] self.vexs = [] self.n = n self.e = edef CreateMatGraph(self,a,n,e): # 創建鄰接矩陣 self.n = n # 頂點數n self.e = e # 邊數e self.edges = copy.deepcopy(a) # 深復制到鄰接矩陣adef DisMatGraph(self): # 輸出圖的鄰接矩陣 for i in range(self.n): for j in range(self.n): if self.edges[i][j] == INF: print("%4s"%("∞"),end='') else: print("%5d"%(self.edges[i][j]),end='') print()# Prim算法構建最小生成樹def Prim(g,v): global min, k lowcost = [0]*MAXV # 建立數組：最小的權值 closest = [0]*MAXV # 建立數組：最近的點 for i in range(g.n): # 給lowcost[]和closest[]置初值，i是某頂點的編號 lowcost[i] = g.edges[v][i] # lowcost[]記錄邊的權值 closest[i] = v # closest[]記錄最近頂點 for i in range(1,g.n): # 找出最小生成樹的所有邊 min = INF # 用INF表示未連接(權值無窮大) k = -1 # 用-1表示邊不存在 for j in range(g.n): # 找出離（選取頂點集）U最近的頂點k if lowcost[j] != 0 and lowcost[j]<min: # 若選取邊的權值小於對應頂點列表中的值 min = lowcost[j] # 則更新數組（最短路徑）值為該邊的權值 k = j # k記錄最小頂點的編號 print("(%d,%d):%d"%(closest[k],k,+min),end='') # 輸出最小生成樹的邊 lowcost[k] = 0 # 更新lowcost數組以記錄改變 for j in range(g.n): # 尋找最小距離數組 if lowcost[j] != 0 and g.edges[k][j] < lowcost[j]: # 判斷最小權值 lowcost[j] = g.edges[k][j] # 修改lowcost closest[j] = k # 修改closestif __name__ == '__main__':
