基于有权图的网络最大流标号算法的研究与实现

周青 杨剑兰

（昆明医科大学海源学院 云南省昆明市 650001）

计算机学科是一门应用性和实用性很强的学科。为了更好地实践“计算思维”的模式，利用计算机学科的基本概念、理论来求解、系统设计解决实际问题。也为了更好地践行“二十大关于新工科建设学科融合”的问题，本文将针对求解网络最大流问题的经典算法标号法，在算法思想和原理的基础上，结合计算机语言程序设计的一般步骤，给出了程序设计的具体流程和部分代码。这一过程，将在程序设计的基本概念和理论，落到实地，真正解决实际问题。

1 有权图的介绍

有权图是图论里一个重要概念，即图的每条边都有一个表示一定实际含义的权数，称为赋权图或者有权图。记作D=(V,A,C)。在具有实际意义的网络中，边上的权值可能表示的是路程，也可能表示的是运输费用。

而网络最大流的问题正是基于有向图的，且与一般的有向图有所不同，任何一个流都从某个点单向流入另一个点，并且追根溯源地来自同一个始点，又去往同一个终点。所有流源头的那个点被称为发点，记作Vs，而流向的那个终点被称为收点，记作Vt，其余各点称为中间点。对于网络中的每一条弧，都存在一个容量，这规定了单条弧中的最大流量。而实际上流过这条弧的流量，不一定会达到容量。因此，在网络最大流问题中，有向图的权值一般用容量和流量来标识。

2 网络最大流标号算法

2.1 网络最大流的概念和模型

最大流问题，是网络流理论研究的一个基本问题：在有若干节点构成的网络中，求一个可行流f，使其流量v(f)在不超过容量上限的前提下，达到最大值，这样的可行流f 称为最大流。网络最大流的问题，属于有特殊限制的线性规划问题，可以建立如下数学模型：

在该数学模型中，其中cij为弧(vi,vj)上的容量，fij为弧(vi,vj)上的流量。i 表示任一中间结点，s 表示开始结点，t 表示终止结点。

2.2 标号算法的介绍

求解网络最大流的问题，可以划归为最优化问题：如何调整网络节点的实际流量，实现在流量守恒和容量约束的前提下流量最大？求解此类问题有很多方法，其中最为著名算法是由Ford 和Fulkerson 提出的标号法。

标号算法的流程图：根据标号算法的迭代过程，画出该算法的流程图如图1。

图1：标号算法流程图

该算法的核心思想是，对于网络上的任何一条由起点到终点的可行流，如果存在一条增广链，那么说明该网络上的流量还没有达到最大，可以继续增加流量。直到找不到增广链为止，最终的网络流量即为最大流。具体分为两个步骤：

（1）标号过程（通过为顶点标号，寻找可能存在的增广链）。

标号信息包括两部分：前置节点和该弧尚可增加的流量值。以节点j 为例，若前置节点为i，标号信息可表示为[vi,θj]。其中θj为调整量，vi 为前一节点，θj为该弧尚可增加的流量值。

可标号原则为：正向弧非饱和，即容量Cij>流量fij，反向弧为非零流弧，即流量fij>0，满足其一方可标号。

具体标号步骤如下：

a．自起始顶点s 开始标号：[VS,∞]

b．选择与顶点关联的各类弧：

c．把顶点集分为两部分：已标号点集和未标号点集。此时的已标号点集可以看作是纳入了已标号顶点的新的更大的“开始节点”。

d．继续重复b 和c 步骤，直到标到终止节点t 为止。此时出现两种可能的结果：

（2）调整过程（调整增广链上的流量）。

调整的流量值取θ=min{θj}

调整完继续重复前面的标号过程，直到没有增广链出现为止，结束算法，当前网络流量即为最大流。

3 JAVA程序设计流程

3.1 算法数据结构选择

为了更好地将有权图在计算机中存储，该算法中引入二维数组（邻接矩阵）的数据结构。

邻接矩阵是表示顶点之间相邻关系的矩阵，在有向图中，常用邻接矩阵来表示。其数据结构常表示为二维数组的形式：

邻接矩阵的引入，更加直观、简单，同时，在做标号算法的迭代时，便于找寻任一顶点的所有“邻接点”（有边直接相连的顶点），提高了程序执行效率。

有如下网络流问题实例：“如何安排fij，可使网络D 上的总流量v 最大？”

以图2 为例，有权图采用邻接矩阵具体表示如图3、图4。

图2：网络流问题实例

图3：基于网络容量的矩阵表示

图4：基于网络流量的矩阵表示

注意：在实际的计算机存储中，为了便于计算，将∞替换为0。

3.2 算法的代码实现

本文根据算法的思想和原理，进而将算法转换为代码，采用Java 语言编辑算法过程，其中运用到的主要数据结构为二维数组，以存储示例邻接矩阵，部分代码如下：

寻找增广链，调整增广链上的流量是该算法的核心，在实际编程中，采用键-值对（key-value）集合Map 存储增广路径的编号，通过编号查找增广路径，利用不会存储重复的元素Set 集合存储当前的增广路径编号的组合顺序，使用for 循环结构以迭代思想求解示例网络流图的最大流流量，核心代码片段如下：

3.3 代码的可行性验证与评价

为了验证程序代码的可行性，本文依然以上文中出现的网络流实例问题（图2）为具体例子，按具体步骤进行标号，将程序运行结果与手动标号结果进行对照。

（1）具体标号过程。

从顶点Vs 开始首次标号，然后，观察与Vs 关联的所有弧，发现只有流出弧，在流出的未饱和弧中，有V1 和V2 两个顶点符合标号规则，选择其一如V1 进行标号，前一节点为Vs，调整量为1；此时，将顶点集划分为已标号和未标号两部分，观察所有从已标号顶点流入未标号顶点的弧，再次判断是否符合标号规则，重复操作，直到标号顶点到达终点Vt 节点位置。

经过第一轮标号，已标号顶点为Vs,V1,V5,V4,Vt具体标号信息如图5所示。

图5

逆向搜索，找到一条增广链。如图6所示。

图6

调整增广链，调整量为增广链上弧流量的最小值，调整后结果如图7。

图7

标号算法二次迭代，自顶点Vs 开始，重复第一次的标号过程，可标号顶点为Vs 和V2，标号过程无法继续进行，算法终止。当前该网络实际流量为最大流量，即4+3+7=14。红色圆圈表示的部分即为最小截的顶点集。如图8所示。

图8

（2）完整JAVA 程序在IDEA 中的运行结果截图如图9。

图9

将算法步骤的具体迭代和程序代码的运行结果二者对照，结果一致，最大流均为14.说明将算法转化后的Java 程序代码是可行的。在解决节点数更多的有权图时，程序代码的执行效率具有明显的优势。

4 总结

本文首先介绍了网络最大流问题的数学模型，然后结合现有的优秀的算法对算法原理进行了流程图转换。并以此为基础，依照程序设计的流程，将该经典算法转化为具体的程序代码，文中展示了部分核心代码。最后，为了更好地验证JAVA 程序的可行性，利用网络最大流问题进行了实例比对，通过比较，发现程序的运行结果和算法步骤求解出的结果保持一致。说明该过程是可行的，该程序在解决此类问题中可以较高效地求解出最优化的路径和最大流量。