NetworkX系列教程(10)-算法之四:拓扑排序与最大流问题
重头戏部分来了,写到这里我感觉得仔细认真点了,可能在NetworkX中,实现某些算法就一句话的事,但是这个算法是做什么的,用在什么地方,原理是怎么样的,不清除,所以,我决定先把图论中常用算法弄个明白在写这部分.
图论常用算法看我的博客:
下面我将使用NetworkX实现上面的算法,建议不清楚的部分打开两篇博客对照理解.
我将图论的经典问题及常用算法的总结写在下面两篇博客中:
图论—问题篇
图论—算法篇
目录:
* 11.4拓扑排序算法(TSA)
* 11.5最大流问题
注意:如果代码出现找不库,请返回第一个教程,把库文件导入.
11.4拓扑排序算法(TSA)
- DG = nx.DiGraph([(\’a\’, \’b\’), (\’a\’, \’c\’),(\’b\’, \’e\’), (\’b\’, \’d\’),(\’c\’, \’e\’), (\’c\’, \’d\’),(\’d\’, \’f\’), (\’f\’, \’g\’), (\’e\’, \’g\’)])
-
-
#显示graph
- nx.draw_spring(DG,with_labels=True)
- plt.title(\’有向无环图\’,fontproperties=myfont)
- plt.axis(\’on\’)
- plt.xticks([])
- plt.yticks([])
- plt.show()
-
-
#这个graph拓扑排序序列有很多,这里只给出一种
- print(\’扑排序序列:\’,list(nx.topological_sort(DG)))
- print(\’逆扑排序序列:\’,list(reversed(list(nx.topological_sort(DG)))))
拓扑排序算法示例
输出:
拓扑序序列: [\’a\’, \’b\’, \’c\’, \’e\’, \’d\’, \’f\’, \’g\’]
逆拓扑序序列: [\’g\’, \’f\’, \’d\’,\’e\’, \’c\’, \’b\’, \’a\’]
11.5最大流问题
-
#构建graph
- G = nx.DiGraph()
- G.add_edge(\’x\’,\’a\’, capacity=3.0)
- G.add_edge(\’x\’,\’b\’, capacity=1.0)
- G.add_edge(\’a\’,\’c\’, capacity=3.0)
- G.add_edge(\’b\’,\’c\’, capacity=5.0)
- G.add_edge(\’b\’,\’d\’, capacity=4.0)
- G.add_edge(\’d\’,\’e\’, capacity=2.0)
- G.add_edge(\’c\’,\’y\’, capacity=2.0)
- G.add_edge(\’e\’,\’y\’, capacity=3.0)
- pos=nx.spring_layout(G)
-
-
#显示graph
- edge_labels = nx.get_edge_attributes(G,\’capacity\’)
- nx.draw_networkx_nodes(G,pos)
- nx.draw_networkx_labels(G,pos)
- nx.draw_networkx_edges(G,pos)
- nx.draw_networkx_edge_labels(G, pos,edge_labels)
- plt.axis(\’on\’)
- plt.xticks([])
- plt.yticks([])
- plt.show()
-
-
#求最大流
- flow_value, flow_dict = nx.maximum_flow(G, \’x\’, \’y\’)
- print(“最大流值: “,flow_value)
- print(“最大流流经途径: “,flow_dict)
最大流问题示例
输出:
最大流值: 3.0
最大流流经途径: {\’x\’: {\’a\’: 2.0, \’b\’: 1.0}, \’c\’: {\’y\’: 2.0}, \’b\’: {\’c\’: 0, \’d\’: 1.0}, \’y\’: {}, \’d\’: {\’e\’: 1.0}, \’e\’: {\’y\’: 1.0}, \’a\’:{\’c\’: 2.0}}
版权声明：本文为wushaogui原创文章，遵循 CC 4.0 BY-SA 版权协议，转载请附上原文出处链接和本声明。