数据结构与算法 / 系统课时

残量网络

残量网络

残量网络把“还能继续发送多少流量”和“已经发送的流量能撤销多少”统一成一张可继续搜索的图。理解它之后,最大流算法中的改路、回退与重新分配就不再是额外规则,而只是沿残量边进行普通更新。

学习目标

  • 计算正向残量容量与反向残量容量。
  • 解释反向残量边为何能够撤销已有流量。
  • 根据当前容量和流量构造完整残量网络。

正向与反向残量边

设原网络中存在有向边 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 的边,并检查任意一对方向的更新是否满足“正向减少多少,反向就增加多少”。

本课练习

  1. 将示例中 A -> B 的流量改为 4,重新计算并核对正向、反向残量容量。验收条件是 A -> B 不再出现在可用正向边中,而 B -> A 的残量容量变为 4。
  2. 为程序增加 applyResidualStep(from, to, amount) 方法,使它能够沿正向或反向残量边更新原流量。要求拒绝超过残量容量的操作,并在更新后验证所有原边仍满足容量限制。

本课总结

  • 一条原边会贡献正向剩余容量 c - f 和反向可撤销容量 f。
  • 反向残量边的本质是减少原方向的已有流量,而不是发送负流量。
  • 正反两个方向必须同步更新,残量网络才能支持后续改路。

下一课预告

下一课将学习“增广路径”,把残量容量串成从源点到汇点的可行路径,并通过瓶颈容量完成一轮流量更新。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

残量网络

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通