引言

Prim算法與Dijkstra的最短路徑算法類似，它采用貪心策略。算法開始先把圖中權值最小的邊添加到樹T中，然后不斷把權值最小的邊E（E的一個端點在T中，另一個在G-T中）。當沒有符合條件的E時算法結束，此時T就是G的一個最小生成樹。

NetworkX是一款Python的軟件包，用于創造、操作復雜網絡，以及學習復雜網絡的結構、動力學及其功能。 本文借助networkx.Graph類實現Prim算法。

正文

Prim算法的代碼

Prim

def prim(G, s): dist = {} # dist記錄到節點的最小距離 parent = {} # parent記錄最小生成樹的雙親表 Q = list(G.nodes()) # Q包含所有未被生成樹覆蓋的節點 MAXDIST = 9999.99 # MAXDIST表示正無窮，即兩節點不鄰接 # 初始化數據 # 所有節點的最小距離設為MAXDIST，父節點設為None for v in G.nodes():  dist[v] = MAXDIST  parent[v] = None # 到開始節點s的距離設為0 dist[s] = 0 # 不斷從Q中取出“最近”的節點加入最小生成樹 # 當Q為空時停止循環，算法結束 while Q:  # 取出“最近”的節點u，把u加入最小生成樹  u = Q[0]  for v in Q:   if (dist[v] < dist[u]):    u = v  Q.remove(u)  # 更新u的鄰接節點的最小距離  for v in G.adj[u]:   if (v in Q) and (G[u][v]['weight'] < dist[v]):    parent[v] = u    dist[v] = G[u][v]['weight'] # 算法結束，以雙親表的形式返回最小生成樹 return parent

測試數據

測試代碼

import matplotlib.pyplot as pltimport networkx as nxg_data = [(1, 2, 1.3), (1, 3, 2.1), (1, 4, 0.9), (1, 5, 0.7), (1, 6, 1.8), (1, 7, 2.0), (1, 8, 1.8), (2, 3, 0.9), (2, 4, 1.8), (2, 5, 1.2), (2, 6, 2.8), (2, 7, 2.3), (2, 8, 1.1), (3, 4, 2.6), (3, 5, 1.7), (3, 6, 2.5), (3, 7, 1.9), (3, 8, 1.0), (4, 5, 0.7), (4, 6, 1.6), (4, 7, 1.5), (4, 8, 0.9), (5, 6, 0.9), (5, 7, 1.1), (5, 8, 0.8), (6, 7, 0.6), (6, 8, 1.0), (7, 8, 0.5)]def draw(g): pos = nx.spring_layout(g) nx.draw(g, pos, /   arrows=True, /   with_labels=True, /   nodelist=g.nodes(), /   style='dashed', /   edge_color='b', /   width=2, /   node_color='y', /   alpha=0.5) plt.show()g = nx.Graph()g.add_weighted_edges_from(g_data)tree = prim(g, 1)mtg = nx.Graph()mtg.add_edges_from(tree.items())mtg.remove_node(None)draw(mtg)