本文主要讲解最大流问题的Ford-Fulkerson解法。可以说这是一种方法，而不是算法，因为它包含具有不同运行时间的几种实现。该方法依赖于三种重要思想：残留网络，增广路径和割。
在介绍着三种概念之前，我们先简单介绍下Ford-Fulkerson方法的基本思想。首先需要了解的是Ford-Fulkerson是一种迭代的方法。开始时，对所有的u,v属于V，f(u,v)=0(这里f(u,v)代表u到v的边当前流量)，即初始状态时流的值为0。在每次迭代中，可以通过寻找一个“增广路径”来增加流值。增广路径可以看做是从源点s到汇点t之间的一条路径，沿该路径可以压入更多的流，从而增加流的值。反复进行这一过程，直到增广路径都被找出为止。
举个例子来说明下，如图所示，每条红线就代表了一条增广路径，当前s到t的流量为3。
当然这并不是该网络的最大流，根据寻找增广路径的算法我们其实还可以继续寻找增广路径，最终的最大流网络如下图所示，最大流为4。
接下来我们就介绍如何寻找增广路径。在介绍增广路径之前，我们首先需要介绍残留网络的概念。
残留网络
顾名思义，残留网络是指给定网络和一个流，其对应还可以容纳的流组成的网络。具体说来，就是假定一个网络G=（V，E），其源点s，汇点t。设f为G中的一个流，对应顶点u到顶点v的流。在不超过C（u，v）的条件下（C代表边容量），从u到v之间可以压入的额外网络流量，就是边（u，v）的残余容量（residual capacity），定义如下：
r（u，v）=c（u，v）-f（u，v）
举个例子，假设（u，v）当前流量为3/4，那么就是说c（u，v）=4，f（u，v）=3，那么r（u，v）=1。
我们知道，在网络流中还有这么一条规律。从u到v已经有了3个单位流量，那么从反方向上看，也就是从v到u就有了3个单位的残留网络，这时r（v，u）=3。可以这样理解，从u到v有3个单位流量，那么从v到u就有了将这3个单位流量的压回去的能力。
我们来具体看一个例子，如下图所示一个流网络
其对应的残留网络为：
增广路径
在了解了残留网络后，我们来介绍增广路径。已知一个流网络G和流f，增广路径p是其残留网络Gf中从s到t的一条简单路径。形象的理解为从s到t存在一条不违反边容量的路径，向这条路径压入流量，可以增加整个网络的流值。上面的残留网络中，存在这样一条增广路径：
其可以压入4个单位的流量，压入后，我们得到一个新的流网络，其流量比原来的流网络要多4。这时我们继续在新的流网络上用同样的方法寻找增广路径，直到找不到为止。这时我们就得到了一个最大的网络流。
流网络的割
上面仅仅是介绍了方法，可是怎么证明当无法再寻找到增广路径时，就证明当前网络是最大流网络呢？这就需要用到最大流最小割定理。
首先介绍下，割的概念。流网络G（V，E）的割（S，T）将V划分为S和T=V-S两部分，使得s属于S，t属于T。割（S，T）的容量是指从集合S到集合T的所有边（有方向）的容量之和（不算反方向的，必须是S-àT）。如果f是一个流，则穿过割（S，T）的净流量被定义为f（S，T）（包括反向的，SàT的为正值，T—>S的负值）。将上面举的例子继续拿来，随便画一个割，如下图所示：
割的容量就是c(u,w)+c(v,x)=26
当前流网络的穿过割的净流量为f(u,w)+f(v,x)-f(w,v)=12+11-4=19
显然，我们有对任意一个割，穿过该割的净流量上界就是该割的容量，即不可能超过割的容量。所以网络的最大流必然无法超过网络的最小割。
可是，这跟残留网络上的增广路径有什么关系呢？
首先，我们必须了解一个特性，根据上一篇文章中讲到的最大流问题的线性规划表示时，提到，流网络的流量守恒的原则，根据这个原则我们可以知道，对网络的任意割，其净流量的都是相等的。具体证明是不难的，可以通过下图形象的理解下，
和上面的割相比，集合S中少了u和v，从源点s到集合T的净流量都流向了u和v，而在上一个割图中，集合S到集合T的流量是等于u和v到集合T的净流量的。其中w也有流流向了u和v，而这部分流无法流向源点s，因为没有路径，所以最后这部分流量加上s到u和v的流量，在u和v之间无论如何互相传递流，最终都要流向集合T，所以这个流量值是等于s流向u和v的值的。将s比喻成一个水龙头，u和v流向别处的水流，都是来自s的，其自身不可能创造水流。所以任意割的净流量都是相等的。
万事俱备，现在来证明当残留网络Gf中不包含增广路径时，f是G的最大流。
假设Gf中不包含增广路径，即Gf不包含从s到v的路径，定义S={v:Gf中从s到v存在一条通路}，也就是Gf中s能够有通路到达的点的集合，显然这个集合不包括t，因为s到t没有通路。这时，我们令T=V-S。那么（S，T）就是一个割。如下图所示：
那么，对于顶点u属于S，v属于T，有f（u，v）=c（u，v）。否则（u，v）就存在残余流量，因而s到u加上u到v就构成了一条s到v的通路，所以v就必须属于S，矛盾。因此这时就表明当前流f是等于当前的割的容量的，因此f就是最大流。
Ford-Fulkerson方法
Ford-Fulkerson方法的正确性依赖于这个定理：当残存网络中不存在一条从s到t的增广路径，那么该图已经达到最大流。这个定理的证明及一些与其等同的定理可以参考《算法导论》。
Ford-Fulkerson方法的伪代码如下。其中<u,v>代表顶点u到顶点v的一条边，<u,v>.f表示该边的流量，c是边容量矩阵，c(i,j)表示边<i,j>的容量，当边<i,j>不存在时，c(i,j)=0。e为残存网络矩阵，e(i,j)表示边<i,j>的值，当边<i,j>不存在时，e(i,j)=0。E表示边的集合。f表示流网络。
Ford-Fulkerson
for <u,v> ∈ E
<u,v>.f = 0
while find a route from s to t in e
m = min(<u,v>.f, <u,v> ∈ route)
for <u,v> ∈ route
if <u,v> ∈ f
<u,v>.f = <u,v>.f + m
else
<v,u>.f = <v,u>.f - m
Ford-Fulkerson方法首先对图中的所有边的流量初始化为零值，然后开始进入循环：如果在残存网络中可以找到一条从s到t的增广路径，那么要找到这条这条路径上值最小的边，然后根据该值来更新流网络。
Ford-Fulkerson有很多种实现，主要不同点在于如何寻找增广路径。最开始提出该方法的Ford和Fulkerson同学在其论文中都是使用广度优先搜索实现的，其时间复杂度为O(VE)，整个算法的时间复杂度为O(VE^2)。
代码实现
Edge:
package com.darrenchan.graph.FordFulkerson; /**
* 网络中的边
*/
public class Edge { private int v1;
private int v2;
private int capacity;
private int flow; public Edge(int v1,int v2,int flow,int capacity){
this.v1 = v1;
this.v2 = v2;
this.capacity = capacity;
this.flow = flow;
} public int getV1(){
return v1;
} public int getV2(){
return v2;
} public int getCapacity(){
return capacity;
} public int getFlow(){
return flow;
} public void setFlow(int f){
flow = f;
}
}
Edge2:
package com.darrenchan.graph.FordFulkerson; /**
* 残存网络中的边
*/
public class Edge2 {
private int v1;
private int v2;
private int flow; public Edge2(int v1,int v2,int flow){
this.v1 = v1;
this.v2 = v2;
this.flow = flow;
} public int getV1(){
return v1;
} public int getV2(){
return v2;
} public int getFlow(){
return flow;
} public void setFlow(int f){
flow = f;
}
}
Gf:
package com.darrenchan.graph.FordFulkerson; import java.util.LinkedList;
import java.util.Queue; public class Gf {
private int vNum;
private int eNum;
private LinkedList<Edge2>[] GLists; public Gf(int n){
vNum = n;
eNum = 0;
GLists = new LinkedList[n]; for(int i = 0;i<n;i++)
GLists[i] = new LinkedList<>();
} public void insertEdge(Edge2 e){
int v1 = e.getV1();
GLists[v1].add(e);
eNum++;
} /**
* 返回一条增广路径
* @return
*/
public LinkedList<Integer> augmentingPath(){ LinkedList<Integer> list = new LinkedList<>();
Queue<Integer> queue = new LinkedList<>();
int[] reached = new int[vNum];
int[] preNode = new int[vNum];
for(int i = 0;i<vNum;i++){
reached[i] = 0;
preNode[i] = -1;
}
preNode[0] = -1; reached[0] = 1;
queue.add(0);
while(!queue.isEmpty()){//没有循环起来
int now = queue.poll(); LinkedList<Edge2> inlist = (LinkedList<Edge2>) GLists[now].clone(); while(!inlist.isEmpty()){ Edge2 e = inlist.pop();
int v2 = e.getV2(); if(reached[v2]==0){
queue.add(v2);
reached[v2] = 1;
preNode[v2] = now;
}
}
} for(int i = 0;i<vNum;i++){
System.out.println(reached[i]+" "+preNode[i]);
} if(reached[vNum-1]==0){
//System.out.println("here");
return list; } int pointnum = vNum-1;
while(pointnum!=-1){
list.add(0, pointnum);
pointnum = preNode[pointnum];
} return list;
} /**
* 根据增广路径得到需要调整的值
* 找到增广路径中最小的边
* @param list
* @return
*/
public int changeNum(LinkedList<Integer> list){
if(list.equals(null))
return 0;
int minchange = 1000;
int v1 = 0;
for(int i = 1;i<list.size();i++){
int v2 = list.get(i);
LinkedList<Edge2> elist = (LinkedList<Edge2>) GLists[v1].clone();
Edge2 edge = elist.pop();
while(edge.getV2()!=v2){
edge = elist.pop();
}
if(minchange>edge.getFlow())
minchange = edge.getFlow(); v1 = v2;
} return minchange;
} public void bianli(){
System.out.println("残存网络 共 "+vNum+" 个顶点， "+eNum+" 条边");
for(int i = 0;i<vNum;i++){
if(GLists[i].size()==0){
System.out.println(i+"没有后继");
continue;
}
for(int j = 0;j<GLists[i].size();j++){
Edge2 e = GLists[i].get(j);
System.out.println("[ "+e.getV1()+" , "+e.getV2()+" , "+e.getFlow()+" ]");
}
}
} }
Graph:
package com.darrenchan.graph.FordFulkerson;
import java.util.LinkedList;
public class Graph {
private int vNum;
private int eNum;
private Gf gf;
private LinkedList<Edge>[] GLists;
public Graph(int n){
vNum = n;
eNum = 0;
GLists = new LinkedList[n];
for(int i = 0;i<n;i++)
GLists[i] = new LinkedList<>();
}
public void insertEdge(Edge e){
int v1 = e.getV1();
GLists[v1].add(e);
eNum++;
}
public void produceGf(){
gf = new Gf(vNum);
for(int i = 0;i<vNum;i++){
LinkedList<Edge> list = (LinkedList<Edge>) GLists[i].clone();
while(!list.isEmpty()){
Edge edge = list.pop();
int v1 = edge.getV1();
int v2 = edge.getV2();
int flow = edge.getFlow();
int capacity = edge.getCapacity();
if(flow==0){
gf.insertEdge(new Edge2(v1,v2,capacity));
}else{
if(flow==capacity){
gf.insertEdge(new Edge2(v2,v1,capacity));
}else if(flow<capacity){
gf.insertEdge(new Edge2(v1,v2,capacity-flow));
gf.insertEdge(new Edge2(v2,v1,flow));
}
}
}
}
}
public Gf getGf(){
return gf;
}
private LinkedList<Integer> augmentingPath(){
return gf.augmentingPath();
}
private int changeNum(LinkedList<Integer> list){
return gf.changeNum(list);
}
/**
* 最大流
*/
public void MaxFlow(){
produceGf();
gf.bianli();
LinkedList<Integer> list = augmentingPath();
while(list.size()>0){
int changenum = changeNum(list);
LinkedList<Integer> copylist = (LinkedList<Integer>) list.clone();//调试
System.out.println("list:");
while(!copylist.isEmpty()){
System.out.print(copylist.pop()+" ");
}
System.out.println();
System.out.println("changenum: "+changenum);
int v1 = 0;
for(int i = 1;i<list.size();i++){
int v2 = list.get(i);
if(!GLists[v1].isEmpty()){
int j = 0;
Edge e = GLists[v1].get(j);
while(e.getV2()!=v2 && j<GLists[v1].size()){
e = GLists[v1].get(j);
j++;
}
if(e.getV2()!=v2 && j==GLists[v1].size()){//调试
j = 0;
e = GLists[v2].get(j);
while(e.getV2()!=v1 && j<GLists[v2].size()){
e = GLists[v2].get(j);
j++;
}
}
e.setFlow(e.getFlow()+changenum);
}
v1 = v2;
}
bianli();
produceGf();
gf.bianli();
list = augmentingPath();
}
}
public void bianli(){
System.out.println("共有 "+vNum+" 个顶点， "+eNum+" 条边");
for(int i = 0;i<vNum;i++){
if(GLists[i].size()==0)
continue;
for(int j = 0;j<GLists[i].size();j++){
Edge e = GLists[i].get(j);
System.out.println("[ "+e.getV1()+" , "+e.getV2()+" , "+e.getFlow()+" , "+e.getCapacity()+" ]");
}
}
}
public void showResult(){
bianli();
int maxflow = 0;
for(int i = 0;i<vNum;i++){
if(GLists[i].size()>0){
for(int j = 0;j<GLists[i].size();j++){
if(GLists[i].get(j).getV2() == vNum-1){
maxflow += GLists[i].get(j).getFlow();
}
}
}
}
System.out.println("最大流为 "+maxflow);
}
}
Main:
package com.darrenchan.graph.FordFulkerson;
public class Main {
public static void main(String[] args){
test();
}
private static void test(){
Graph graph = new Graph(6);
Edge[] edges = new Edge[9];
edges[0] = new Edge(0,1,0,16);
edges[1] = new Edge(0,2,0,13);
edges[2] = new Edge(1,3,0,12);
edges[3] = new Edge(2,1,0,4);
edges[4] = new Edge(2,4,0,14);
edges[5] = new Edge(3,2,0,9);
edges[6] = new Edge(3,5,0,20);
edges[7] = new Edge(4,3,0,7);
edges[8] = new Edge(4,5,0,4);
for(int i = 0;i<9;i++)
graph.insertEdge(edges[i]);
graph.MaxFlow();
graph.showResult();
}
public static void test2(){
Graph graph = new Graph(6);
Edge[] edges = new Edge[9];
edges[0] = new Edge(0,1,4,16);
edges[1] = new Edge(0,2,0,13);
edges[2] = new Edge(1,3,4,12);
edges[3] = new Edge(2,1,0,4);
edges[4] = new Edge(2,4,4,14);
edges[5] = new Edge(3,2,4,9);
edges[6] = new Edge(3,5,0,20);
edges[7] = new Edge(4,3,0,7);
edges[8] = new Edge(4,5,4,4);
for(int i = 0;i<9;i++)
graph.insertEdge(edges[i]);
graph.bianli();
graph.MaxFlow();
graph.bianli();
}
}
运行结果：
残存网络 共 6 个顶点， 9 条边
[ 0 , 1 , 16 ]
[ 0 , 2 , 13 ]
[ 1 , 3 , 12 ]
[ 2 , 1 , 4 ]
[ 2 , 4 , 14 ]
[ 3 , 2 , 9 ]
[ 3 , 5 , 20 ]
[ 4 , 3 , 7 ]
[ 4 , 5 , 4 ]
5没有后继
1 -1
1 0
1 0
1 1
1 2
1 3
list:
0 1 3 5
changenum: 12
共有 6 个顶点， 9 条边
[ 0 , 1 , 12 , 16 ]
[ 0 , 2 , 0 , 13 ]
[ 1 , 3 , 12 , 12 ]
[ 2 , 1 , 0 , 4 ]
[ 2 , 4 , 0 , 14 ]
[ 3 , 2 , 0 , 9 ]
[ 3 , 5 , 12 , 20 ]
[ 4 , 3 , 0 , 7 ]
[ 4 , 5 , 0 , 4 ]
残存网络 共 6 个顶点， 11 条边
[ 0 , 1 , 4 ]
[ 0 , 2 , 13 ]
[ 1 , 0 , 12 ]
[ 2 , 1 , 4 ]
[ 2 , 4 , 14 ]
[ 3 , 1 , 12 ]
[ 3 , 2 , 9 ]
[ 3 , 5 , 8 ]
[ 4 , 3 , 7 ]
[ 4 , 5 , 4 ]
[ 5 , 3 , 12 ]
1 -1
1 0
1 0
1 4
1 2
1 4
list:
0 2 4 5
changenum: 4
共有 6 个顶点， 9 条边
[ 0 , 1 , 12 , 16 ]
[ 0 , 2 , 4 , 13 ]
[ 1 , 3 , 12 , 12 ]
[ 2 , 1 , 0 , 4 ]
[ 2 , 4 , 4 , 14 ]
[ 3 , 2 , 0 , 9 ]
[ 3 , 5 , 12 , 20 ]
[ 4 , 3 , 0 , 7 ]
[ 4 , 5 , 4 , 4 ]
残存网络 共 6 个顶点， 13 条边
[ 0 , 1 , 4 ]
[ 0 , 2 , 9 ]
[ 1 , 0 , 12 ]
[ 2 , 0 , 4 ]
[ 2 , 1 , 4 ]
[ 2 , 4 , 10 ]
[ 3 , 1 , 12 ]
[ 3 , 2 , 9 ]
[ 3 , 5 , 8 ]
[ 4 , 2 , 4 ]
[ 4 , 3 , 7 ]
[ 5 , 3 , 12 ]
[ 5 , 4 , 4 ]
1 -1
1 0
1 0
1 4
1 2
1 3
list:
0 2 4 3 5
changenum: 7
共有 6 个顶点， 9 条边
[ 0 , 1 , 12 , 16 ]
[ 0 , 2 , 11 , 13 ]
[ 1 , 3 , 12 , 12 ]
[ 2 , 1 , 0 , 4 ]
[ 2 , 4 , 11 , 14 ]
[ 3 , 2 , 0 , 9 ]
[ 3 , 5 , 19 , 20 ]
[ 4 , 3 , 7 , 7 ]
[ 4 , 5 , 4 , 4 ]
残存网络 共 6 个顶点， 13 条边
[ 0 , 1 , 4 ]
[ 0 , 2 , 2 ]
[ 1 , 0 , 12 ]
[ 2 , 0 , 11 ]
[ 2 , 1 , 4 ]
[ 2 , 4 , 3 ]
[ 3 , 1 , 12 ]
[ 3 , 2 , 9 ]
[ 3 , 5 , 1 ]
[ 3 , 4 , 7 ]
[ 4 , 2 , 11 ]
[ 5 , 3 , 19 ]
[ 5 , 4 , 4 ]
1 -1
1 0
1 0
0 -1
1 2
0 -1
共有 6 个顶点， 9 条边
[ 0 , 1 , 12 , 16 ]
[ 0 , 2 , 11 , 13 ]
[ 1 , 3 , 12 , 12 ]
[ 2 , 1 , 0 , 4 ]
[ 2 , 4 , 11 , 14 ]
[ 3 , 2 , 0 , 9 ]
[ 3 , 5 , 19 , 20 ]
[ 4 , 3 , 7 , 7 ]
[ 4 , 5 , 4 , 4 ]
最大流为 23
参考：
https://blog.csdn.net/john_bian/article/details/74734243