于晓倩 陈燕 李龙霞

（大连海事大学航运经济与管理学院 辽宁省大连市 116026）

1 序言

结构化程序设计的先驱Niklaus Wirth曾提出：程序=数据结构+算法。实际问题通过获得相应的计算机外部逻辑表示，转化为计算机内部存储结构，辅以算法，即可得到解决。现实中许多系统都存在着各种各样的流，如公路系统中有车辆流，水利系统中有水流，电力系统中有电流，等等。各种流汇集成连通网络，网络中每条边的最大通过能力是有限的，实际流量不能超过其容量。基于这一前提，可以解决许多实际工程类问题。

最大流问题以图论的知识为理论基础，应用极为广泛，20世纪50年代福特(Ford)、富克逊(Fulkerson)建立的“网络流理论”，是网络应用的重要组成部分。基本的最大流问题就是通过充分利用装置的能力使得运输的流量最大。目前这一问题已经有许多算法可以解决，如EK算法、SAP算法、DINIC算法、HLPP算法等。本文是从管理运筹学中的福特-富尔克逊标号法提炼出算法，利用数据结构中的图结构自主解决最大流问题。

2 问题背景与分析

为解决山区水资源运输问题，现从出发地途经各村庄，使得水资源运送至目的地时水流量最大。根据数据结构思想建模，可以将各村庄抽象为顶点，根据流的流向以及运输路径，可以将流抽象为带权重的弧其中r为容量，x为当前流量，构成有向网。那么最大流问题就可以利用图论知识来解决。图是一种数据结构，加上一组基本操作，就构成了抽象数据类型：