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

Algorithm and Its Implementation for the Network Maximal Flow

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

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.