[1]赵礼峰 盂晓婉.基于深度优先的一种网络最大流求解法[J].计算机技术与发展,2012,(10):161-164.
　ZHAO Li-feng,MENG Xiao-wan.An Algorithm for Solving Maximum Flow Based on Depth First Search[J].,2012,(10):161-164.
点击复制

基于深度优先的一种网络最大流求解法()
分享到：

《计算机技术与发展》[ISSN:1006-6977/CN:61-1281/TN]

卷:
期数:
2012年10期
页码:
161-164
栏目:
智能、算法、系统工程
出版日期:
1900-01-01

文章信息/Info

Title:
An Algorithm for Solving Maximum Flow Based on Depth First Search
文章编号:
1673-629X（2012）10-0161-04
作者:
赵礼峰 盂晓婉
南京邮电大学理学院
Author(s):
ZHAO Li-feng;  MENG Xiao-wan
College of Mathematics and Physics, Nanjing University of Posts and Telecommunications
关键词:
最大流; 增广链; 增广链算法; 深度优先搜索
Keywords:
maximum flow ;  augmenting path;  augmenting path algorithm;  depth first search
分类号:
TP301.6
文献标志码:
A
摘要:
网络最大流问题在工程和科学领域应用广泛，许多线性规划的实际问题都可转化为网络最大流的模型来求解．开辟了图论应用的新途径。为了解决现有的求解网络最大流算法存在的步骤繁复、计算量大、由于增广链选取的顺序不当而无法得到理想的最大流等问题，文中在原有算法的基础上作了一些改进，应用图的深度优先搜：泰原理，提出一种新的求解最大流问题的算法。该算法可以简单快速地找到增广链，提高了算法效率和可控性，易于实现，且避免了标号过程，只需要在一个图上即可完成，整个运算过程直观性强，计算方便
Abstract:
The network of maximum flow is widely applied in engineering and science, a lot of the actual linear programming problem can be converted into the network of the maximum flow model to solve, opened up a new way of the application of graph theory. There are lots of steps and complicated calculation in the existing algorithm for solving the maximum networks flow, and because of improper selection order of augmented path, can not obtain the ideal maximum flow. In order to solve these problems in existing algorithm, it does some improvement of the existing algorithms, then puts forward a new algorithm for solving the maximum flow problem which makes use of depth first search theory. This algorithm can find the augmented path easily and quickly, and avoid the labeling process, the entire operation process only needs drawing a diagram to be completed,it is improving the efficiency and controllable of the algorithm and easy to realize. It is strong intuitive and convenient to calculate

相似文献/References:

[1]赵礼峰,纪亚宝. 最大流问题的改进最短增广链算法[J].计算机技术与发展,2016,26(08):52.
　ZHAO Li-feng,JI Ya-bao. Improved Shortest Augmenting Chain Algorithm of Maximum Flow[J].,2016,26(10):52.
[2]赵礼峰,纪亚劲. 基于最短增广链的最大流改进算法[J].计算机技术与发展,2017,27(08):88.
　ZHAO Li-feng,JI Ya-jin. Improved Algorithm of Maximum Flow with Shortest Augmenting Chain[J].,2017,27(10):88.
[3]邵丽萍,赵礼峰.最大流问题的最短增广链改进算法[J].计算机技术与发展,2019,29(05):58.[doi:10. 3969 / j. issn. 1673-629X. 2019. 05. 012]
　SHAO Li-ping,ZHAO Li-feng.Shortest Augmented Chain Improvement Algorithm for Maximum Flow Problem[J].,2019,29(10):58.[doi:10. 3969 / j. issn. 1673-629X. 2019. 05. 012]
[4]邵丽萍,赵礼峰.基于宽度优先的网络最大流求解算法[J].计算机技术与发展,2019,29(06):62.[doi:10. 3969 / j. issn. 1673-629X. 2019. 06. 013]
　SHAO Li-ping,ZHAO Li-feng.An Algorithm for Solving Maximum Flow Based on Breadth First Search[J].,2019,29(10):62.[doi:10. 3969 / j. issn. 1673-629X. 2019. 06. 013]
[5]罗甜甜,赵礼峰.基于重置顶点下标的网络最大流算法[J].计算机技术与发展,2020,30(10):26.[doi:10. 3969 / j. issn. 1673-629X. 2020. 10. 005]
　LUO Tian-tian,ZHAO Li-feng.A Network Maximum Flow Algorithm Based on Reset Vertex Subscript[J].,2020,30(10):26.[doi:10. 3969 / j. issn. 1673-629X. 2020. 10. 005]
[6]赵礼峰 陈华 宋常城 白睿.基于一个网络图最大流算法的改进[J].计算机技术与发展,2010,(12):162.
　ZHAO Li-feng,CHEN Hua,SONG Chang-cheng,et al.Improvement of an Algorithm Solving Maximum Flow Based on a Network Diagram[J].,2010,(10):162.
[7]赵礼峰 白睿 宋常城.求解网络最大流问题的标号算法[J].计算机技术与发展,2011,(12):113.
　ZHAO Li-feng,BAI Rui,SONG Chang-cheng.Labeling Algorithm to Solve Maximum Network Flow Problem[J].,2011,(10):113.
[8]赵礼峰,董方.一种求解网络图最大流的新算法[J].计算机技术与发展,2014,24(02):120.
　ZHAO Li-feng,DONG Fang.A New Algorithm for Solving Maximum Flow[J].,2014,24(10):120.
[9]赵礼峰,陶晓莉. 网络最大流问题的改进算法[J].计算机技术与发展,2014,24(11):54.
　ZHAO Li-feng,TAO Xiao-li. An Improved Algorithm for Solving Problem of Network Maximum Flow[J].,2014,24(10):54.

备注/Memo

备注/Memo:
国家自然科学基金资助项目（61070234,61071167）赵礼峰（1959-），男，安徽淮北人，教授，硕士研究生导师，研究方向为图论及其应用
更新日期/Last Update: 1900-01-01