数据结构与算法 / 系统课时
残量网络
残量网络
残量网络把“还能继续发送多少流量”和“已经发送的流量能撤销多少”统一成一张可继续搜索的图。理解它之后,最大流算法中的改路、回退与重新分配就不再是额外规则,而只是沿残量边进行普通更新。
学习目标
- 计算正向残量容量与反向残量容量。
- 解释反向残量边为何能够撤销已有流量。
- 根据当前容量和流量构造完整残量网络。
正向与反向残量边
设原网络中存在有向边 u -> v,容量为 c,当前流量为 f,并满足 0 <= f <= c。残量网络会从这条边派生出两个方向的可用容量。
| 残量方向 | 残量容量 | 表示的操作 |
|---|---|---|
u -> v |
c - f |
继续增加从 u 到 v 的流量 |
v -> u |
f |
撤销一部分已经从 u 到 v 发送的流量 |
当 f = 0 时,反向残量容量为 0;当 f = c 时,正向边已经饱和,但反向边仍允许算法回退。如果原图本来就同时存在 u -> v 和 v -> u,同一方向上的“未使用容量”和“可撤销容量”需要累加到对应残量容量中。

反向边为什么能够改路
反向残量边不是原网络中新建的一条业务边,也不表示允许发送“负流量”。当增广路径沿 v -> u 通过反向边时,含义是把原边 u -> v 上的流量减少同样的数值。算法因此可以撤销较早的局部选择,再把释放出的容量用于另一条更有价值的路径。
一次增广必须沿从源点到汇点的完整残量路径进行,所以对中间顶点而言,增加与撤销会成对发生,流量守恒仍然成立。每次更新后还应继续满足容量限制、非负流量和中间顶点流入等于流出这三类约束。
完整可运行示例
下面的 Java 17 程序根据原边的容量与当前流量构造残量容量矩阵。示例中三条原边都已经发送 3 个单位,因此每条边既有正向剩余容量,也产生了反向可撤销容量。
java
import java.util.List;
public class ResidualNetworkDemo {
static class Edge {
final int from;
final int to;
final int capacity;
final int flow;
Edge(int from, int to, int capacity, int flow) {
if (flow < 0 || flow > capacity) {
throw new IllegalArgumentException("流量必须位于 0 到容量之间");
}
this.from = from;
this.to = to;
this.capacity = capacity;
this.flow = flow;
}
}
public static void main(String[] args) {
String[] names = {"S", "A", "B", "T"};
List<Edge> edges = List.of(
new Edge(0, 1, 5, 3),
new Edge(1, 2, 4, 3),
new Edge(2, 3, 6, 3)
);
int[][] residual = new int[names.length][names.length];
for (Edge edge : edges) {
// 正向残量表示还能追加多少流量。
residual[edge.from][edge.to] += edge.capacity - edge.flow;
// 反向残量表示最多可以撤销多少已有流量。
residual[edge.to][edge.from] += edge.flow;
}
System.out.println("残量网络中的可用边:");
for (int from = 0; from < names.length; from++) {
for (int to = 0; to < names.length; to++) {
if (residual[from][to] > 0) {
System.out.printf("%s -> %s: %d%n",
names[from], names[to], residual[from][to]);
}
}
}
}
}运行命令:
bash
javac ResidualNetworkDemo.java
java ResidualNetworkDemo预期输出:
text
残量网络中的可用边:
S -> A: 2
A -> S: 3
A -> B: 1
B -> A: 3
B -> T: 3
T -> B: 3常见错误与调试
| 错误表现 | 原因 | 修复方式 |
|---|---|---|
| 边饱和后被永久删除 | 只记录了 c - f,没有创建反向残量 |
同时执行 residual[v][u] += f |
| 回退后流量变成负数 | 反向增广量超过当前流量 | 只允许使用残量容量大于 0 的反向边 |
| 后续路径找不到可用边 | 更新时只减少正向残量 | 每次都同步增加对应反向残量 |
| 双向原边的容量被覆盖 | 使用赋值而不是累加 | 构造残量网络时使用 += 合并贡献 |
调试时可以在每轮增广后打印所有残量容量大于 0 的边,并检查任意一对方向的更新是否满足“正向减少多少,反向就增加多少”。
本课练习
- 将示例中
A -> B的流量改为 4,重新计算并核对正向、反向残量容量。验收条件是A -> B不再出现在可用正向边中,而B -> A的残量容量变为 4。 - 为程序增加
applyResidualStep(from, to, amount)方法,使它能够沿正向或反向残量边更新原流量。要求拒绝超过残量容量的操作,并在更新后验证所有原边仍满足容量限制。
本课总结
- 一条原边会贡献正向剩余容量
c - f和反向可撤销容量f。 - 反向残量边的本质是减少原方向的已有流量,而不是发送负流量。
- 正反两个方向必须同步更新,残量网络才能支持后续改路。
下一课预告
下一课将学习“增广路径”,把残量容量串成从源点到汇点的可行路径,并通过瓶颈容量完成一轮流量更新。
按自己的节奏,确认真正理解。