NetworkX之Prim演算法(例項講解)

NetworkX之Prim演算法(例項講解)

引言

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

測試資料

從~到2345678
11.32.10.90.71.82.01.8
20.91.81.22.82.31.1
32.61.72.51.91.0
40.71.61.50.9
50.91.10.8
60.61.0
70.5

測試程式碼


import matplotlib.pyplot as plt
import networkx as nx
g_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)

執行結果

以上這篇NetworkX之Prim演算法(例項講解)就是小編分享給大家的全部內容了,希望能給大家一個參考,也希望大家多多支援指令碼之家。