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

残量网络为什么重要

残量网络为什么重要

最大流不是把某条路选中后就永久锁死。前面的增广可能做出局部选择,后续必须允许撤回并重新分配已有流量。残量网络正是记录“还能继续送多少,以及已经送出的流还能撤回多少”的结构。

学习目标

  • 理解正向残量和反向残量分别表示什么
  • 看懂反向边如何撤销早先的一部分流量
  • 通过一次增广过程观察流量重新分配

残量网络记录“还能怎么改”

对原图中的边 u -> v,若容量为 5、当前已经发送 3,那么正向残量为 2,表示还能继续从 u 向 v 发送 2。与此同时,残量网络会出现 v -> u 的反向容量 3,表示最多可以撤销之前发送的 3。

因此,残量网络不是原网络的副本,而是“当前解附近还允许做哪些修改”的动态图。每次增广后都要同时更新两个方向:正向残量减少,反向残量增加。

两次增广中的残量与反向边

反向边不是额外通道

最容易误解的是把反向边当成原题中真实存在的新通道。它并不是新的运输能力,而是一个“撤销操作”。当增广路经过反向边 v -> u 时,含义是把原来 u -> v 上的一部分流量减掉,再把这部分能力释放出来给其他路径使用。

这也是最大流算法能够修正早期选择的原因。如果没有反向边,一旦第一次增广选错路径,后续就只能在被锁死的局部方案上继续,很可能得不到真正的最大流。

手动演示一次重新分配

下面的网络最多可以从 S 向 T 发送 2 单位流量。我们故意先走 S -> A -> B -> T,这会占用 A -> B。第二次增广必须经过残量边 B -> A,撤销第一次在 A -> B 上的流,才能形成新的分配。

python
from collections import defaultdict

capacity = {
    ("S", "A"): 1,
    ("S", "B"): 1,
    ("A", "B"): 1,
    ("A", "T"): 1,
    ("B", "T"): 1,
}

residual = defaultdict(int)
for (u, v), c in capacity.items():
    residual[(u, v)] = c
    residual[(v, u)] += 0

def augment(path, amount):
    # 更新残量:正向减少,反向增加
    for u, v in zip(path, path[1:]):
        if residual[(u, v)] < amount:
            raise ValueError("insufficient residual capacity")
        residual[(u, v)] -= amount
        residual[(v, u)] += amount

augment(["S", "A", "B", "T"], 1)
print("after first augment: residual B->A =", residual[("B", "A")])

# B->A 是反向边,用它撤销第一次 A->B 的 1 单位流
augment(["S", "B", "A", "T"], 1)

print("final flow:")
for edge in capacity:
    u, v = edge
    flow = capacity[edge] - residual[edge]
    print(f"{u}->{v} {flow}")

print("max flow = 2")

预期输出

text
after first augment: residual B->A = 1
final flow:
S->A 1
S->B 1
A->B 0
A->T 1
B->T 1
max flow = 2

第一次增广后,B -> A 获得 1 单位反向残量。第二次路径使用它,相当于把 A -> B 上原有的 1 单位流撤回,因此最终 A -> B 的净流量重新变成 0,而总流量提升到 2。

增广时真正维护的是什么

实现最大流时,搜索对象始终是“当前残量网络中从 S 到 T 的可行路径”,而不是原图中的固定路径。每找到一条增广路,就取路径上的最小残量作为瓶颈,并对沿途所有边同时执行“正向减、反向加”。

以 Edmonds-Karp 为例,BFS 每次都在残量网络中找边数最少的增广路;其经典时间复杂度为 O(VE²)。理解残量网络后,反向边、撤销旧流和重新分配就会统一成同一套更新规则,而不再是额外特例。

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

目录与阅读设置

阅读设置

17

记录一个想法

残量网络为什么重要

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

登录哪都通