数据结构与算法 / 系统课时
Ford-Fulkerson 方法
Ford-Fulkerson 方法
Ford-Fulkerson 方法把最大流问题化为“寻找增广路径并更新残量网络”的重复过程。本课将用整数容量网络实现完整算法,并说明它何时终止、为什么容量类型会影响可靠性。
学习目标
- 理解增广路径、瓶颈容量和残量网络之间的关系。
- 能够使用深度优先搜索实现 Ford-Fulkerson 方法。
- 判断整数、有理数与无理数容量对终止性的影响。
核心原理
流网络由源点、汇点和带非负容量的有向边组成。合法流必须满足容量限制,并在除源点和汇点之外的每个顶点保持流量守恒。Ford-Fulkerson 不直接修改原容量,而是在残量网络中记录每条边还能增加多少流量。
每轮算法执行三个动作:
- 在残量容量大于 0 的边上寻找一条从源点到汇点的路径。
- 取路径上最小残量容量作为本轮瓶颈流量。
- 减少正向残量并增加反向残量,使后续轮次能够撤销或改道此前的选择。

终止条件与容量限制
当残量网络中不存在源点到汇点的增广路径时,当前流就是最大流。若所有容量都是整数,每轮至少增加 1 个单位,因此算法会在有限轮内结束;使用邻接表寻找路径时,常写作 ,其中 是最大流值,所以它是伪多项式复杂度。
有理数容量可以先按公分母缩放为整数。对于无理数容量,任意选择增广路径的版本可能无限执行,甚至不收敛到最大流。工程实现还要注意浮点误差,通常优先使用整数单位或定点数。
易错点
- 忘记增加反向残量,会失去撤销错误路径选择的能力。
- 直接覆盖原容量,导致无法区分输入数据与当前残量状态。
- 把任意 DFS 路径选择误认为多项式时间保证;该保证属于后续的 Edmonds-Karp 算法。
- 最大流可能超过
int范围时,应把容量、瓶颈和累计流量统一改为long。
完整可运行示例
下面的 Java 17 程序使用邻接矩阵保存容量,并用栈实现 DFS。网络包含源点 0、汇点 3,每次找到路径后立即更新残量矩阵。
java
import java.util.ArrayDeque;
import java.util.Arrays;
import java.util.Deque;
public class FordFulkersonDemo {
public static void main(String[] args) {
int[][] capacity = {
{0, 3, 2, 0},
{0, 0, 1, 2},
{0, 0, 0, 3},
{0, 0, 0, 0}
};
int maxFlow = fordFulkerson(capacity, 0, 3);
System.out.println("最大流: " + maxFlow);
}
static int fordFulkerson(int[][] capacity, int source, int sink) {
int n = capacity.length;
int[][] residual = new int[n][n];
for (int i = 0; i < n; i++) {
residual[i] = Arrays.copyOf(capacity[i], n);
}
int[] parent = new int[n];
int maxFlow = 0;
while (findAugmentingPath(residual, source, sink, parent)) {
int bottleneck = Integer.MAX_VALUE;
for (int v = sink; v != source; v = parent[v]) {
int u = parent[v];
bottleneck = Math.min(bottleneck, residual[u][v]);
}
for (int v = sink; v != source; v = parent[v]) {
int u = parent[v];
residual[u][v] -= bottleneck;
residual[v][u] += bottleneck;
}
maxFlow += bottleneck;
System.out.println("本轮增广流量: " + bottleneck);
}
return maxFlow;
}
static boolean findAugmentingPath(
int[][] residual, int source, int sink, int[] parent) {
Arrays.fill(parent, -1);
boolean[] visited = new boolean[residual.length];
Deque<Integer> stack = new ArrayDeque<>();
stack.push(source);
visited[source] = true;
while (!stack.isEmpty()) {
int u = stack.pop();
for (int v = 0; v < residual.length; v++) {
if (!visited[v] && residual[u][v] > 0) {
parent[v] = u;
visited[v] = true;
stack.push(v);
if (v == sink) {
return true;
}
}
}
}
return false;
}
}运行命令如下:
bash
javac FordFulkersonDemo.java
java FordFulkersonDemo预期输出
text
本轮增广流量: 2
本轮增广流量: 2
本轮增广流量: 1
最大流: 5三轮增广的总量为 2 + 2 + 1 = 5。当 DFS 再也找不到到达汇点的正残量路径时,循环结束。
练习
- 将边
2 -> 3的容量从3改为1,重新运行程序,并解释为什么最大流受汇点入边总容量限制。 - 在输出中加入每轮完整路径,验收条件是路径首点为
0、末点为3,且打印的瓶颈等于该路径最小残量。
本课总结
- Ford-Fulkerson 的本质是不断在残量网络中增广,并用反向边保留改道能力。
- 整数容量保证有限终止,但运行时间依赖最大流数值,不是强多项式界。
- 路径选择策略决定算法行为,任意 DFS 只是该方法的一种实现。
下一课预告
下一课将学习 Edmonds-Karp 算法,用 BFS 固定选择边数最少的增广路径,并推导它为什么具有 的多项式时间上界。
按自己的节奏,确认真正理解。