快捷導(dǎo)航

NetworkX之Prim算法(實(shí)例講解)

更新時(shí)間：2017年12月22日 15:08:10 作者：engreal

下面小編就為大家分享一篇NetworkX之Prim算法實(shí)例講解，具有很好的參考價(jià)值，希望對(duì)大家有所幫助。一起跟隨小編過來看看吧

引言

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

NetworkX是一款Python的軟件包，用于創(chuàng)造、操作復(fù)雜網(wǎng)絡(luò)，以及學(xué)習(xí)復(fù)雜網(wǎng)絡(luò)的結(jié)構(gòu)、動(dòng)力學(xué)及其功能。本文借助networkx.Graph類實(shí)現(xiàn)Prim算法。

正文

Prim算法的代碼

Prim

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

測試數(shù)據(jù)

從~到	2	3	4	5	6	7	8
1	1.3	2.1	0.9	0.7	1.8	2.0	1.8
2		0.9	1.8	1.2	2.8	2.3	1.1
3			2.6	1.7	2.5	1.9	1.0
4				0.7	1.6	1.5	0.9
5					0.9	1.1	0.8
6						0.6	1.0
7							0.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)

運(yùn)行結(jié)果