摘要：图图学JGraphT开源框架是教材《数据结构与算法》-java语言版（清华大学出版社-2024，耿祥义，张跃平）第13章《图论》的课外读物（共计19回25个实例），所以主要围绕教材的内容学习JGraphT开源框架，即学JGraphT开源框架中最重要的部分，不是学习JGraphT开源框架的全部内容（JGraphT开源框架封装关于最短路径的算法类就有30多个）。掌握这里的这些内容，也可以让我们在实际项目更加容易地使用图论的算法，这也正是框架的目的。
图图学开源JGraphT开源框架目录如下：
这是
图图学开源JGraphT的第19回-《最大流算法和EdmondsKarpMFImpl类》，这回学习的主要内容是：
最大流
EdmondsKarpMFImpl类
一、 最大流
最大流问题是指在给定源点和汇点的情况下，找到从源点到汇点的最大流量（简单说，就是找一个顶点到另一个顶点的最大流量）。最大流问题(Maximum Flow Problem)是网络流问题中的一个重要类型。其核心问题是:在一个流网络中，找到源点s到汇点t的最大可能流量。
例如，一个城市的交通网络中的道路可以看作图中的边，路口可以看作图中的顶点。每条道路都有一定的最大通行能力（即容量，即边的权值）：例如每小时最多能通过多少辆车。现在要从一个交通枢纽（源点）向另一个交通枢纽（汇点）运输尽可能多的车辆，这就可以转化为最大流问题。通过计算最大流，可以确定在现有道路条件下，最多能有多少辆车从源点运输到汇点。
流网络:一个有向网络，其中每条边都有一个容量(表示这条边所能承载的最大流量，即权重)，并且存在一个源点s和汇点t（二者之间有至少一条路径）.
流量:每条边上的流量不能超过边的容量。可行流量：流量必须满足两个条件:
1.容量限制:边上的流量不能超过其容量。
2.流量守恒:计算时要保证除源点和汇点之外的所有顶点，其流入量必须等于流出量。
最大流问题的目标找到源点s到汇点t的最大流量。
二、Betweenness Centrality类
EdmondsKarpMFImpl类封装了最大流算法（ Edmonds - Karp 算法）。以下是JGraphT框架的原文解释：
This class computes a maximum flow in a flow networkusing Edmonds-Karp algorithm. Given is a weighted directed or undirected graph G(V
,E
)
G(V,E)with vertex set V
Vand edge set E
E. Each edge e∈E
e∈Ehas an associated non-negative capacity u
e
ue. The maximum flow problem involves finding a feasible flow from a source vertex s
sto a sink vertex t
twhich is maximum. The amount of flow f
e
fethrough any edge e
ecannot exceed capacity u
e
ue. Moreover, flow conservation must hold: the sum of flows entering a node must equal the sum of flows exiting that node, except for the source and the sink nodes.
Mathematically, the maximum flow problem is stated as follows:
max
s.t.
∑
e∈δ
+
(s)
f
e
∑
e∈δ
−
(i)
f
e
=∑
e∈δ
+
(i)
f
e
0≤f
e
≤u
e
∀i∈V
∖{s,t}
∀e∈E
max∑e∈δ+(s)fes.t. ∑e∈δ−(i)fe=∑e∈δ+(i)fe∀i∈V∖{s,t}0≤fe≤ue∀e∈E
Here δ
+
(i)
δ+(i)resp δ
−
(i)
δ−(i)denote resp the outgoing and incoming edges of vertex i
i.
When the input graph is undirected, an edge (i,j)
(i,j)is treated as two directed arcs: (i,j)
(i,j)and (j,i)
(j,i). In such a case, there is the additional restriction that the flow can only go in one direction: the flow either goes form i
ito j
j, or from j
jto i
i, but there cannot be a positive flow on (i,j)
(i,j)and (j,i)
(j,i)simultaneously.
The runtime complexity of this class is O(nm
2
)
O(nm2), where n
nis the number of vertices and m
mthe number of edges in the graph. For a more efficient algorithm, consider using PushRelabelMFImplinstead.
This class can also compute minimum s-t cuts. Effectively, to compute a minimum s-t cut, the implementation first computes a minimum s-t flow, after which a BFS is run on the residual graph.
三、代码与效果
将jgrapht-1.5.2.zip解压后的lib文件夹复制到C:\studyJGrapht，然后在命令行进入开发目录C:\studyJGrapht。(C:\studyJGrapht是作者使用的开发目录，您可以使用任何自己喜欢的开发目录或名称）。
例子19.1 最大流量（效果如图19.1)
如下编译和运行代码。
图19.1 最大流量
Ex19_1.java
