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

测试数据

从~到 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算法(实例讲解)就是小编分享给大家的全部内容了,希望能给大家一个参考,也希望大家多多支持我们。

(0)

相关推荐

  • 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 = {} #

  • JS数组操作中的经典算法实例讲解

    冒泡排序 <script type="text/javascript"> var arr = [3,7,6,2,1,5]; 定义一个交换使用的中间变量 var temp = 0; for(i=0;i<arr.length;i++){ for(j=0;j<arr.length;j++){ 如果下一个元素小于当前元素 if(arr[j]>arr[j+1]){ 互换 temp = arr[j]; arr[j] = arr[j+1]; arr[j+1] = tem

  • SPFA 算法实例讲解

    适用范围:给定的图存在负权边,这时类似Dijkstra等算法便没有了用武之地,而Bellman-Ford算法的复杂度又过高,SPFA算法便 派上用场了. 我们约定有向加权图G不存在负权回路,即最短路径一定存在.当然,我们可以在执行该算法前做一次拓扑排序,以判断是否存在负权回路,但这不是我们讨论的重 点. 算法思想:我们用数组d记录每个结点的最短路径估计值,用邻接表来存储图G.我们采取的方法是动态逼近法:设立一个先进先出的队列用来保存待优化的 结点,优化时每次取出队首结点u,并且用u点当前的最短路

  • C语言杨氏矩阵查找算法实例讲解

    目录 一.杨氏矩阵介绍 二.查找算法 1.查找思路 2.步骤 3.代码 三.杨氏矩阵例题 代码 特别注意 四.总结 本文以C语言实现,介绍杨氏矩阵中通用的查找算法. 一.杨氏矩阵介绍 杨氏矩阵种,每一行的数都从左到右递增,每一列的数都从上到下递增.如下图是一个简单的杨氏矩阵: 有一个数字矩阵,矩阵的每行从左到右是递增的,矩阵从上到下是递增的,请编写程序在这样的矩阵中查找某个数字是否存在. 要求:时间复杂度小于O(N) 二.查找算法 1.查找思路 杨氏矩阵是很有特点的,它有规律递增的特点决定了针对

  • Javascript迭代、递推、穷举、递归常用算法实例讲解

    累加和累积 累加:将一系列的数据加到一个变量里面.最后的得到累加的结果 比如:将1到100的数求累加和 小球从高处落下,每次返回到原来一半,求第十次小球落地时小球走过的路程 <script> var h=100; var s=0; for(var i=0;i<10;i++){ h=h/2; s+=h; } s=s*2+100; </script> 累积:将一系列的数据乘积到一个变量里面,得到累积的结果. 常见的就是n的阶乘 var n=100; var result= 1;

  • Prim(普里姆)算法求最小生成树的思想及C语言实例讲解

    Prim 算法思想: 从任意一顶点 v0 开始选择其最近顶点 v1 构成树 T1,再连接与 T1 最近顶点 v2 构成树 T2, 如此重复直到所有顶点均在所构成树中为止. 最小生成树(MST):权值最小的生成树. 生成树和最小生成树的应用:要连通n个城市需要n-1条边线路.可以把边上的权值解释为线路的造价.则最小生成树表示使其造价最小的生成树. 构造网的最小生成树必须解决下面两个问题: 1.尽可能选取权值小的边,但不能构成回路: 2.选取n-1条恰当的边以连通n个顶点: MST性质:假设G=(V

  • java排序算法之_选择排序(实例讲解)

    选择排序是一种非常简单的排序算法,从字面意思我们就可以知道,选择就是从未排序好的序列中选择出最小(最大)的元素,然后与第 i 趟排序的第 i-1(数组中下标从 0 开始) 个位置的元素进行交换,第 i 个元素之前的序列就是已经排序好的序列.整个排序过程只需要遍历 n-1 趟便可排好,最后一个元素自动为最大(最小)值. 举个小例子: arr[] = {3,1,2,6,5,4} 第 1 趟排序: index = 0, min = 1, 交换后 -->  1,3,2,6,5,4 第 2 趟排序: in

  • 对python数据切割归并算法的实例讲解

    当一个 .txt 文件的数据过于庞大,此时想要对数据进行排序就需要先将数据进行切割,然后通过归并排序,最终实现对整体数据的排序.要实现这个过程我们需要进行以下几步:获取总数据行数:根据行数按照自己的需要对数据进行切割:对每组数据进行排序 最后对所有数据进行归并排序. 下面我们就来实现这整个过程: 一:获取总数据的行 def get_file_lines(file_path): # 目标文件的路径 file_path = str(file_path) with open(file_path, 'r

  • python归并排序算法过程实例讲解

    关于python的算法一直都是让我们又爱又恨,但是如果可以灵活运用起来,对我们的编写代码过程,可以大大提高效率,针对算法之一"归并排序"的灵活掌握,一起来看下吧~ 归并算法--小试牛刀 实例内容: 有 1 个无序列表如下: list = [23,35,12,34,54,78,76,99] 要求:使其按从小到大排序 图示思路 Python 代码 归并排序理解: 1.通过二分法把一个数组按照递归拆分为左右两组(至到独立元素为止) 2.按照从底层往高层的方法左右数组对比,同时对两个数组的第一

  • Java算法之数组冒泡排序代码实例讲解

    冒泡排序是数组查找算法中最为简单的算法 冒泡排序原理: 假设一个数组长度为k(最高索引k-1),遍历前k - 1个(最高索引k-2)元素,若数组中的元素a[i]都与相邻的下一个元素a[i+1]进行比较,若a[i] > a[i+1] ,则这两个元素交换位置.以此类推,若a[i+1] > a[i+2],则交换位置-直至a[k-2]与a[k-1]比较完毕后,第0轮迭代结束.此时,a[k-1]为数组元素中的最大值. 第1轮迭代,再对数组a的前k-1个元素重复进行以上操作. - 第k-2轮迭代,对数组a

随机推荐