基于深度优先的一种网络最大流求解法

• 作者: 孟晓婉 赵礼峰
• 来源期刊: 计算机技术与发展
• 学科: 工学
• 关键词: 最大流 增广链 增广链算法 深度优先搜索
• 年，卷（期）: 2012,（10）
• 页码范围: 161-164
• 分类号: TP301.6
• 字数: 2839字
• 语种: 中文

摘要

网络最大流问题在工程和科学领域应用广泛,许多线性规划的实际问题都可转化为网络最大流的模型来求解,开辟了图论应用的新途径.为了解决现有的求解网络最大流算法存在的步骤繁复、计算量大、由于增广链选取的顺序不当而无法得到理想的最大流等问题,文中在原有算法的基础上作了一些改进,应用图的深度优先搜索原理,提出一种新的求解最大流问题的算法.该算法可以简单快速地找到增广链,提高了算法效率和可控性,易于实现,且避免了标号过程,只需要在一个图上即可完成,整个运算过程直观性强,计算方便.

作者信息

序号	姓名	单位	发文数	被引次数	H指数	G指数
1	赵礼峰	南京邮电大学理学院	47	251	9.0	12.0
2	孟晓婉	南京邮电大学理学院	1	9	1.0	1.0