引言
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
测试数据
从~到
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)
运行结果
以上这篇NetworkX之Prim算法(实例讲解)就是小编分享给大家的全部内容了，希望能给大家一个参考，也希望大家多多支持。
NetworkX,Prim算法
免责声明：本站文章均来自网站采集或用户投稿，网站不提供任何软件下载或自行开发的软件！ 如有用户或公司发现本站内容信息存在侵权行为，请邮件告知！ 858582#qq.com
《魔兽世界》大逃杀！60人新游玩模式《强袭风暴》3月21日上线
暴雪近日发布了《魔兽世界》10.2.6 更新内容，新游玩模式《强袭风暴》即将于3月21 日在亚服上线，届时玩家将前往阿拉希高地展开一场 60 人大逃杀对战。
艾泽拉斯的冒险者已经征服了艾泽拉斯的大地及遥远的彼岸。他们在对抗世界上最致命的敌人时展现出过人的手腕，并且成功阻止终结宇宙等级的威胁。当他们在为即将于《魔兽世界》资料片《地心之战》中来袭的萨拉塔斯势力做战斗准备时，他们还需要在熟悉的阿拉希高地面对一个全新的敌人──那就是彼此。在《巨龙崛起》10.2.6 更新的《强袭风暴》中，玩家将会进入一个全新的海盗主题大逃杀式限时活动，其中包含极高的风险和史诗级的奖励。
《强袭风暴》不是普通的战场，作为一个独立于主游戏之外的活动，玩家可以用大逃杀的风格来体验《魔兽世界》，不分职业、不分装备（除了你在赛局中捡到的），光是技巧和战略的强弱之分就能决定出谁才是能坚持到最后的赢家。本次活动将会开放单人和双人模式，玩家在加入海盗主题的预赛大厅区域前，可以从强袭风暴角色画面新增好友。游玩游戏将可以累计名望轨迹，《巨龙崛起》和《魔兽世界：巫妖王之怒 经典版》的玩家都可以获得奖励。