基于栈的网络最大流算法

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

New max-flow algorithm in network based on stack

Facing the question of max-flow in network,based on cut set define and max-flow rain-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 ca-pacity 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 net-work,and breaks the localization of cut set define and max-flow rain-cut theorem that have only theory value,do not solve practie 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.