基于标号法求解最大流问题的算法研究

于晓倩 陈燕 李龙霞

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

1 序言

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

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

2 问题背景与分析

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

图的物理结构比较复杂。由于无法以数据元素在存储区中的物理位置来表示元素之间的联系，所以图没有顺序存储结构，但可以借助二维数组来表示（如邻接矩阵），以及链式存储（如邻接表等）来进行存储。具体可参考严蔚敏版《数据结构》第六章。

3 案例分析与实现

3.1 案例描述

某山区水源不足，现欲将水流从临河村庄A运输至村庄F，途经村庄B、C、D、E。部分村子之间铺设有管道，管道的运输能力（即容量）不同。各村之间的实际管道情况如图1所示，试求从A村运输到F村的最大水流量。

图1：村庄间管道详情

3.2 案例分析

观察易知，该问题属于图的应用，逻辑结构为图。由于图有向且边也存储了相关信息，确定为有向网，可使用邻接矩阵或邻接表来存储。

邻接矩阵与邻接表各有使用环境与优缺点。如邻接矩阵适用于稠密图且便于判断两顶点间是否有边，但空间复杂度高等；邻接表则适用于稀疏图且空间效率高，但不便于确定两点间是否有边等。计算可得上图边数，为稀疏图，暂选用邻接表进行存储。

分析整个标号法，就是从始点v0出发，标记后压入标记栈并将所得信息压入中间栈；若标记栈不空，则弹出顶点并寻找其邻接点判断是否被标记；若未被标记，则按公式（1）求得两点间弧的最大调整量b(vj)（寻找邻接点时只判断是否邻接，并不确定弧的方向，因此弧的方向不同，b(vj)的计算方式不同），并将信息压入栈。

所有顶点判断完毕后，读取中间栈顶信息，若终点vt也被标记，则记调整量θ=b(vt)；不断弹出中间栈信息，从vt开始，不断回溯至第一个标号，就能得到一条由标号点和相应弧连接而成的、从v0到vt的增广链μ。对增广链上各弧的流量按公式（2）进行调整；调整后从始点重新开始，直至找不到增广链（即终点vt未被标记），此时根据始点的流出量或终点的汇集量求和即得最大流量值。

基于以上分析，需要一个标记栈来确定顶点标号的顺序；一个visited数组来标志该顶点是否已经被标号；一个中间栈来保存顶点的标号信息。标记栈只需存储顶点数据即可。因为增广链是从vt回溯到第一个标号点v0，因此中间栈需保存的信息应包括前一点vi、当前标记点vj以及该边(vi, vj)上的最大可调整量b(vj)；根据公式（1），b(vj)的获得需要与b(vi)进行比较，因为栈只能读取栈顶元素，无法做到随机存取，因此还需定义一个flag数组来随机存取每个顶点的b值。此过程需判断关联弧是否存在，邻接矩阵比邻接表更容易实现查找确认，因此最终图的存储结构确定为邻接矩阵：其中，r为总容量，x为当前流量

图2：算法流程图

3.3 算法步骤与流程图

（1）从始点v0出发，将始点压入标记栈，始点的初始信息压入中间栈，置visited[v]的值为TRUE，flag[v]值为∞。

（2）只要标记栈不空，则重复下述操作：

1.弹出标记栈顶元素v；

2.一次将v的所有邻接点w压入邻接点栈；

3.只要邻接点栈不空；

4.弹出邻接点栈顶元素w，如果visited[w]的值为FALSE，且能求得顶点w的新信息(start,end,value)，则将w压入标记栈，将新信息压入中间栈；置visited[w]的值为TRUE，flag[v]值为value；

（3）标记栈为空时，判断终点是否被标记，如果visited[G.vexnum-1]值为TRUE，则寻得增广链并改变增广链上弧的流量，从(1)重新开始。

（4）如果visited[G.vexnum-1]值为FALSE，即可根据始点的流出量或终点的汇集量得最大流量。

图2中(1)-(4)与算法步骤相对应。

3.4 算法实现过程

3.4.1 初始条件

对图3左图求最大流，弧权值如(9,7)，9为容量，7为当前流量。其邻接矩阵如图3右图所示。

3.4.2 操作过程

（1）首先进行初始化数组：visited[]来标识顶点是否被标记；flag[]来保存相应弧上的最大可调整量。如图4所示。

图3：有向网及其邻接矩阵存储

图4：初始化数组

图5：第一次尝试标记顶点

图6：第一次调整增广链

图7：程序运行结果

（2）第一次尝试标记顶点，最终结果如图5所示。

此时循环尚未结束，但visited数组已全为1，说明顶点已全部标记，剩余只有弹出栈操作，直至标记栈a为空。a栈空后，判断是否visited[5]=1，若为1，则说明终点被标记，存在增广链，进入调整增广链过程。

（3）第一次调整增广链，如图6所示。

3.2.3 程序运行结果

如图7所示。

4 总结与展望

通过对数据结构课程的学习，结合管理运筹学科知识，完成了这次独立自主解决实际问题的尝试。通过尝试，理清了解决问题的基本步骤：按照问题描述，建立相应模型，确定计算机外部的逻辑结构，根据实际需求转化为计算机内部存储结构，编写算法形成程序，最终解决问题；对数据结构有了更深层次的理解，为之后的学习打下了一定的基础。

确定计算机外部逻辑结构时，要抓住本质，进行合理地抽象。本文案例相对明显，可以容易地确定为图结构。实际问题大多数要抽象得多，如工作分配问题等。确定逻辑结构后选定内部存储结构时，要充分考虑各种情况，不同的存储结构有各自的优点和适用情况。例如本文中图选用邻接矩阵或者邻接表存储都可以，但考虑到算法中需要多次确定两顶点间是否存在有向弧，这时邻接矩阵就要比邻接表要方便得多。在解决问题的基础上，一个优秀的算法还需要考虑时间复杂度和空间复杂度，进而对算法不断进行优化，本文算法还有很大的改进空间，仍需进一步思考尝试。