摘要
针对网络最大流的计算问题,提出了一种网络最大流计算模型的实现方法.具体作法是灵活运用栈和结构数组以实现算法功能.首先创建邻接表,其结构包含边的方向、容量、流量等信息.然后根据邻接表采用标号法寻找增广链,在寻找过程中采用深度优先遍历和广度优先遍历的方法把点存入栈中,并用一数组保存所经过的路径.直至找出最大流及各边的流量.
On the algorithm of the network maximal flow, the paper provides a method of achieving it. The concrete procedure is to achieve the algorithm by using stack and structural array. First of all, an adjacency list should be established and its composition chiefly includes orientation, capacity, flux and so on. Afterwards the labeling method is adopted to find the augmenting chain according to the adjacency list. In the process, some spots are stored in the stack by means of the depth superior traverse and range superior traverse and the course way is also conserved in the array. Keep on doinh this till the maximum flow and the flow of each arc are all found.
出处
《重庆大学学报(自然科学版)》
EI
CAS
CSCD
北大核心
2006年第5期132-134,共3页
Journal of Chongqing University
基金
河南省自然基金项目(0511010100)
郑州轻工业学院科研基金项目(2004012)
关键词
最大流
增广链
标号法
邻接表
结构数组
maximal flow
augmenting chain
label method
adjacency list
structural array