下面小编就为大家分享一篇NetworkX之Prim算法实例讲解，具有很好的参考价值，希望对大家有所帮助。一起跟随小编过来看看吧
引言
Prim算法与Dijkstra的最短路径算法类似，它采用贪心策略。算法开始先把图中权值最小的边添加到树T中，然后不断把权值最小的边E（E的一个端点在T中，另一个在G-T中）。来源gaodaima#com搞(代@码网当没有符合条件的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算法(实例讲解)的详细内容，更多请关注gaodaima搞代码网其它相关文章！
搞代码网（gaodaima.com）提供的所有资源部分来自互联网，如果有侵犯您的版权或其他权益，请说明详细缘由并提供版权或权益证明然后发送到邮箱[email protected]，我们会在看到邮件的第一时间内为您处理，或直接联系QQ：872152909。本网站采用BY-NC-SA协议进行授权
转载请注明原文链接：NetworkX之Prim算法(实例讲解)
转载请注明原文链接：NetworkX之Prim算法(实例讲解)
