专题进阶 · 图算法推荐总顺序 · 第 62 / 148 课

用残量边表达可追加与可撤销的流,推导增广路径和最小割证书。

先学会这些,再进入本课 广度优先搜索 最大匹配
还有 2 节先修课未标记掌握;已具备基础时可以直接学习,遇到障碍再沿链接补课。
专题详解 · 图算法

网络流Network Flow

在容量约束与流量守恒下最大化源到汇流量,残量图允许修正已有分配。

建议 50 分钟 · 含手算、代码与三层练习

本课要建立的能力

用残量边表达可追加与可撤销的流,推导增广路径和最小割证书。

先手算,再对照代码;理解为什么成立,最后用改变条件的练习检查迁移能力。

01先把问题说具体

管道有容量上限,源点持续供水、汇点收水,中间节点不能凭空造水。怎样求最大总流量?

02一步步得到方法

容量、流量与守恒分别约束什么

每条边的流不能超过容量;除源汇外,流入量等于流出量。路径增广沿源到汇路径统一增加 delta,内部节点同时多流入和流出,因此保持守恒。delta 不能超过路径最小剩余容量,即瓶颈。

残量图正向容量为还可以增加多少,反向容量为可以撤销多少。反向边不是原管道突然允许倒流水,而是算法允许修正以前的分配;这正对应匹配中的重新安排。

为什么用 BFS 找增广路

Edmonds–Karp 每次在残量图按边数找最短增广路,取得多项式复杂度保证。每次沿 parent 追溯路径,找瓶颈,然后正向减去、反向加上。

当残量图里源点到不了汇点,取从源可达集合 S,所有从 S 到外部的边已饱和。当前流值等于该割容量,任何流都不可能超过割容量,因此得到最大流与最小割的共同证书。

残量边是撤销决定的能力

向 u→v 送入流量后,正向残量减少、反向残量增加。反向边不是额外真实管道,而是允许把先前送出的部分流量撤回,再改走其他路径。

增广量取整条路径的最小残量,它是瓶颈;路径每条边都按同一个量更新,内部节点的流入流出因此保持平衡。只改正向、不加反向残量会把早期选择锁死。

03把一个小例子完全算清楚

边 s→a:3、s→b:2、a→b:1、a→t:2、b→t:3。

步骤计算与状态为什么这样做
路径 s–a–t瓶颈 2,累计流 2反向残量边同时增加
路径 s–b–t瓶颈 2,累计流 4b→t 余量 1
路径 s–a–b–t瓶颈 1,累计流 5用尽 s 的总容量
无增广路源点出割容量 3+2=5证明最优

窄屏可左右滑动表格,阅读完整计算与理由。

只在正向边上贪心而不保留撤销能力,可能得到非最大流。

04为什么这个方法成立

  1. 每次增广不超过瓶颈,所以容量约束保持。
  2. 路径内部增量流入等于增量流出,守恒保持;反向残量操作合法撤销旧流。
  3. 无增广路时可达割容量等于流值,结合任意流不超过任意割,证明最优。

05把推导翻译成代码

Python · 可独立运行的教学实现

from collections import deque
def max_flow(n, edges, source, sink):
    assert source != sink
    residual = [[0]*n for _ in range(n)]
    for u,v,c in edges:
        assert c >= 0
        residual[u][v] += c
    total = 0
    while True:
        parent = [-1]*n; parent[source] = source
        q = deque([source])
        while q and parent[sink] == -1:
            u = q.popleft()
            for v in range(n):
                if parent[v] == -1 and residual[u][v] > 0:
                    parent[v] = u; q.append(v)
        if parent[sink] == -1:
            return total
        amount, v = float("inf"), sink
        while v != source:
            u = parent[v]
            amount = min(amount, residual[u][v]); v = u
        v = sink
        while v != source:
            u = parent[v]
            residual[u][v] -= amount
            residual[v][u] += amount
            v = u
        total += amount

逐个理解关键决定

residual[v][u] += amount
创建可撤销的反向容量,缺少它会让算法卡在错误早期选择。
parent[source] = source
源点预先标记,避免残量反向边把源点再次入队。

06时间、空间与实现范围

Edmonds–Karp 用邻接表通常为 O(VE²)。本演示使用 V×V 矩阵,每次 BFS O(V²),配合 O(VE) 次增广给 O(V³E) 保守上界。

矩阵空间 O(V²),适合小图手算;大图应改邻接边结构并成对保存反向边索引。

07改变条件,检查哪里会出错

只减正向容量,不加反向容量

丢失重排能力,不能保证最大流。

把最大流等同最短路径

目标是总可通过量,增广路长度只是选择策略。

容量矩阵覆盖平行边

多条同方向边的容量应聚合或独立表示,简单赋值会丢掉先前容量。

08从手算到独立迁移

先写出自己的结果和理由,再展开提示或解析。三题依次检查具体执行、边界条件和方法迁移。

练习 1 · 复现与理解

源点所有出边容量合计 7,最大流可超过 7 吗?

需要一点提示

把源点单独作为割。

查看解析与答案

不能,该割给出上界 7。

练习 2 · 边界与辨析

一条路径容量为 5、2、8,能增广多少?

需要一点提示

取瓶颈。

查看解析与答案

2。

练习 3 · 变式与迁移

二分匹配怎么建流网络?

需要一点提示

每个节点最多使用一次。

查看解析与答案

源到左侧容量 1,合法配对边容量 1,右侧到汇容量 1;最大整数流等于最大匹配数。

继续深入这个专题

本站例子、推导与教学代码独立编写。以下是相关教材、作者论文或官方文档,可继续核对定义、证明与更完整的工程实现。

Princeton · 图算法

理解之后,继续递进

继续当前专题:最小生成树 →。跨专题先修要求会在下一课顶部提示。

能解释手算中的每一步,并独立完成迁移题后,再标记掌握。