网络最大流模型算法及其实现  

Algorithm and Its Implementation for the Network Maximal Flow

作　　者：张静[1] 邱学绍[2] 

机构地区：[1]同济大学软件学院,上海201800 [2]郑州轻工业学院信息与计算科学系,郑州450002

出　　处：《重庆大学学报（自然科学版）》2006年第5期132-134,共3页Journal of Chongqing University

基　　金：河南省自然基金项目(0511010100);郑州轻工业学院科研基金项目(2004012)

摘　　要：针对网络最大流的计算问题,提出了一种网络最大流计算模型的实现方法.具体作法是灵活运用栈和结构数组以实现算法功能.首先创建邻接表,其结构包含边的方向、容量、流量等信息.然后根据邻接表采用标号法寻找增广链,在寻找过程中采用深度优先遍历和广度优先遍历的方法把点存入栈中,并用一数组保存所经过的路径.直至找出最大流及各边的流量.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.

关 键 词：最大流 增广链 标号法 邻接表 结构数组 

分 类 号：TP319[自动化与计算机技术—计算机软件与理论] O22[自动化与计算机技术—计算机科学与技术]