Computer Engineering and Applications ›› 2009, Vol. 45 ›› Issue (33): 13-15.DOI: 10.3778/j.issn.1002-8331.2009.33.005

• 博士论坛 • Previous Articles     Next Articles

New max-flow algorithm in network based on stack

SHE Xiang-yang   

  1. Computer Science and Technology College,Xi’an University of Science and Technology,Xi’an 710054,China
  • Received:2009-08-07 Revised:2009-09-27 Online:2009-11-21 Published:2009-11-21
  • Contact: SHE Xiang-yang

基于栈的网络最大流算法

厍向阳   

  1. 西安科技大学 计算机科学与技术学院,西安 710054
  • 通讯作者: 厍向阳

Abstract: Facing the question of max-flow in network,based on cut set define and max-flow min-cut theorem,with adjacency matrix to deposit network data,using the data structure of stack to organise network data,traversing all cut sets,the minimum capacity in all cut sets is max-flow in network.The other branches,besides the branches of the minimum cut set,are calculated by solving the node flow balance equation in network.The algorithm pioneers a new way to solve the question of max-flow in network,and breaks the localization of cut set define and max-flow min-cut theorem that have only theory value,do not solve practic max-flow in network.The key branches in network that decide max-flow in network are made easily by the way of the minimum cut set.The direct technology support for enlarging max-flow in network is provided by the algorithm.Algorithm testing shows:The new max-flow algorithm in network based on stack is completely feasible and available.

Key words: max-flow in network, cut set, stack, max-flow min-cut theorem

摘要: 针对网络最大流问题,在割集定义和最大流-最小割定理基础上,以邻接矩阵为网络数据存储结构,利用栈作为数据组织形式,遍历网络中所有割集,最小容量的割集即为网络最大流。流量网络其余分支流量由网络结点流量平衡条件来求解。该算法具有:开辟了一种求解流量网络最大流的新的方法,克服了割集和最大流-最小割定理仅仅具有理论价值、没有实用价值的局限性;根据最小容量的割集可以方便确定决定网络最大流的关键分支,为扩展网络流量提供直接技术支持。算法测试表明:基于栈的网络最大流算法是完全可行和有效的。

关键词: 网络最大流, 割集, 栈, 最小容量割集

CLC Number: