NetworkX系列教程(10)-算法之二:最小/大生成树问题
2024-08-27 02:23:01
小书匠 Graph 图论
重头戏部分来了,写到这里我感觉得仔细认真点了,可能在NetworkX中,实现某些算法就一句话的事,但是这个算法是做什么的,用在什么地方,原理是怎么样的,不清除,所以,我决定先把图论
中常用算法弄个明白在写这部分.
图论常用算法看我的博客:
下面我将使用NetworkX实现上面的算法,建议不清楚的部分打开两篇博客对照理解.
我将图论的经典问题及常用算法的总结写在下面两篇博客中:
图论---问题篇
图论---算法篇
目录:
* 11.2最小/最大生成树问题
* 11.2.1最小生成树
* 11.2.2最大生成树
注意:如果代码出现找不库,请返回第一个教程,把库文件导入.
11.2最小/最大生成树问题
先构建graph,后面最小最大生成树在这个graph上求.
- #生成graph
- G.clear()
- G = nx.Graph()
- G.add_weighted_edges_from([('0','1',2),('0','2',7),('1','2',3),('1','3',8),('1','4',5),('2','3',1),('3','4',4)])
- #边和节点信息
- edge_labels = nx.get_edge_attributes(G,'weight')
- labels={'0':'0','1':'1','2':'2','3':'3','4':'4'}
- #生成节点位置
- pos=nx.spring_layout(G)
- #把节点画出来
- nx.draw_networkx_nodes(G,pos,node_color='g',node_size=500,alpha=0.8)
- #把边画出来
- nx.draw_networkx_edges(G,pos,width=1.0,alpha=0.5,edge_color=['b','r','b','r','r','b','r'])
- #把节点的标签画出来
- nx.draw_networkx_labels(G,pos,labels,font_size=16)
- #把边权重画出来
- nx.draw_networkx_edge_labels(G, pos, edge_labels)
- #显示graph
- plt.title('有权图',fontproperties=myfont)
- plt.axis('on')
- plt.xticks([])
- plt.yticks([])
- plt.show()
最小/最大生成树示例
注:基本上,图示的红色线是最小生成树,蓝色是最大生成树,最小最大生成树都包含1-2这条边
11.2.1最小生成树
- #求得最小生成树,algorithm可以是kruskal,prim,boruvka一种,默认是kruskal
- KA = nx.minimum_spanning_tree(G,algorithm='kruskal')
- print(KA.edges(data=True))
- #直接拿到构成最小生成树的边,algorithm可以是kruskal,prim,boruvka一种,默认是kruskal
- mst = nx.minimum_spanning_edges(G, algorithm='kruskal', data=False)
- edgelist = list(mst)
- print(edgelist)
输出:
- [('3', '4', {'weight': 4}), ('3', '2', {'weight': 1}), ('0', '1', {'weight': 2}), ('2', '1', {'weight': 3})]
- [('3', '2'), ('0', '1'), ('1', '2'), ('4', '3')]
11.2.2最大生成树
- #返回无向图G上的最大生成树或森林。
- T = nx.maximum_spanning_tree(G)
- print(sorted(T.edges(data=True)))
- #直接拿到构成最大生成树,algorithm可以是kruskal,prim,boruvka一种,默认是kruskal
- mst = nx.tree.maximum_spanning_edges(G, algorithm='kruskal', data=False)
- edgelist = list(mst)
- print(edgelist)
输出:
- [('0', '2', {'weight': 7}), ('1', '4', {'weight': 5}), ('2', '1', {'weight': 3}), ('3', '1', {'weight': 8})]
最新文章
- JS实现页面进入、返回定位到具体位置
- HTML核心元素
- javascript eval和JSON之间的联系
- java:利用xpath删除xml中的空节点
- Java 自动装箱与拆箱
- cocos2dx 3.x(移动修改精灵坐标MoveTo与MoveBy)
- OC中修饰符:宏define 常量:const extern
- asp.net常用字符串函数
- android事件系列-onTouch事件与手势操作
- 通过xslt把xml转换成html
- scala函数进阶与lazy的作用
- Naive Bayes在mapreduce上的实现(转)
- yii框架数据库操作数据访问对象(DAO)简单总结
- Java课程设计 学生基本信息管理个人博客
- navcat无法远程连接mysql数据库解决办法
- VueJs(5)---V-bind指令
- 记Javascript一道题的理解
- Linux printf命令详解
- os_mudule_docs
- Screen2EXE录屏|录制视频
热门文章
- java使用poi操作word, 支持动态的行(一个占位符插入多条)和表格中动态行, 支持图片
- vue 等比例截图组件,支持缩放和旋转
- Luogu3824 [NOI2017]泳池 【多项式取模】【递推】【矩阵快速幂】
- Luogu5280 [ZJOI2019] 线段树 【线段树】
- hdu 1242 不用标记数组的深搜
- VsCode开发Angular的必备插件
- VS.NET(C#)--1.3_VS2005开始
- ajax提交异常解决
- entity-framework-core – 实体框架核心RC2表名称复数
- R_数据操作_初级_03