算法与数据结构 · 第 30 课

Edmonds–Karp:为什么用 BFS 找增广路,就能摆脱最大流数值 F?

2026 年 11 月 18 日|第 5 周 · 第 2 天|讲授约 17 分钟,自测另计

昨天的 Ford–Fulkerson 只要求“找到任意一条残量增广路”,整数容量时可得到 O((n+m)F) 上界。问题是:如果容量数值很大,F 也可能很大;如果容量允许一般实数,任意选路甚至可能不终止。今天只修改选路规则:始终用 BFS 选择残量网络中边数最少的 s→t 增广路。这就是 Edmonds–Karp。它的关键不是每次送更多流,而是残量网络的 BFS 层数只能朝一个方向演化。

一、学习目标与模型(约 1 分钟)

本课完成后,应能:(1)区分“最少边数”与“最大瓶颈”;(2)用 BFS 找增广路并维护正反残量弧;(3)手工追踪多轮增广及最终最小割;(4)证明 BFS 最短距离单调不降、关键弧的饱和次数为 O(n);(5)推导 O(nm²) 时间界及其适用边界。

设网络有 n= V 个顶点、m= E 条有向原始边,源点 s≠t,每条容量 c(e)≥0。用 f(e) 表示原边流量,并满足容量约束与除 s,t 外的流守恒。容量不要求为整数;理论证明假设有限的非负实数和精确算术。把原边 (u,v) 的正反残量分别记为 c(u,v)−f(u,v) 和 f(u,v),每条残量弧都具有独立的配对反向弧引用。

二、从 Ford–Fulkerson 到 Edmonds–Karp(约 2 分钟)

昨天的反例告诉我们,原始正向余量不足,不代表残量网络里没有增广路,因为反向残量弧可以撤销旧流量并重新分配。Ford–Fulkerson 允许 DFS、BFS 或任意合法选路;不同选择可能使迭代次数差异很大。

Edmonds–Karp(EK)规定:每轮只对残量容量大于 0的弧运行 BFS,找到从 s 到 t 的最少边数路径,然后沿这条路径以最大瓶颈 Δ 增广。注意两个目标并不相同:BFS 先最小化路径的边数(hop count),不是路径容量之和;找到路径以后,再计算 Δ=min(路径上各残量容量),不是在所有路径里挑最大的 Δ。

这个规则会带来一个重要现象:某条残量弧被饱和以后,即使将来又能使用,同一方向再次成为瓶颈时,其所在的 BFS 层数必须明显增加。

三、示意图与三次增广 Trace(约 3 分钟)

考虑五条有向原边,标签是容量。初始全部流量为 0,BFS 的固定邻接扫描顺序为:s 先 a 后 b;a 先 t 后 b;b 先 t。

flowchart LR
    S((s)) -->|"3"| A((a))
    S -->|"2"| B((b))
    A -->|"2"| T((t))
    A -->|"1"| B
    B -->|"3"| T
增广前 BFS 路径 t 的 BFS 层数 瓶颈 Δ 增广后的总流值
第 1 次:s→a→t 2 2 2
第 2 次:s→b→t 2 2 4
第 3 次:s→a→b→t 3 1 5

第一轮后 a→t 饱和;第二轮后 s→b 饱和,此时 s→a 还剩 1、a→b 还剩 1、b→t 还剩 1,所以第三轮走三条边。最终原边流量为:

原边 s→a s→b a→t a→b b→t
容量 3 2 2 1 3
最终流量 3 2 2 1 3

全部五条边都饱和了,但这不是算法必须满足的普遍性质;在这个例子中是碰巧如此。第三轮后 s 已无正残量出弧,从 s 在残量网络只能到达 s 自己。于是 S={s} 构成一个割,其容量为 c(s,a)+c(s,b)=3+2=5,正好等于流值 5。

这一 Trace 展示了最短边数可以保持相同,也可以增加,却不会减少;这正是下一个证明的起点。

四、核心实现:残量弧成对更新(约 2 分钟)

EDMONDS_KARP(G, s, t):
    为每条原边 (u,v,c) 建立配对残量弧:
        forward(u,v).cap = c
        reverse(v,u).cap = 0
    flow = 0

    while true:
        parent_arc = BFS(s, 只沿 cap > 0 的残量弧)
        if t 未被 BFS 发现:
            break

        Δ = +INF
        v = t
        while v != s:
            a = parent_arc[v]
            Δ = min(Δ, a.cap)
            v = a.from

        v = t
        while v != s:
            a = parent_arc[v]
            a.cap -= Δ
            reverse(a).cap += Δ
            v = a.from
        flow += Δ

    S = BFS_REACHABLE(s, 只沿 cap > 0 的残量弧)
    return flow, S

parent_arc[v] 必须记录具体残量弧及反向配对索引,而不仅是前驱顶点。这样即使原图同时有 u→v 和 v→u 两条真实边,或者存在平行边,也能正确区分并更新。零残量弧不能进入 BFS。

流可行性不变量: 初始零流可行;沿正残量弧增广 Δ 不超过正向未用容量,沿反向残量弧则撤销不超过原有流量;每个中间点的净流入和净流出变化相同,源点净流出增加 Δ、汇点净流入增加 Δ。因此每次仍是可行流,总流值严格上升。

五、第一个证明:BFS 距离为什么不会下降?(约 3 分钟)

令 d_f(v) 为当前残量网络中从 s 到 v 的最少边数;不可达时为 +∞。某次 EK 增广完成前后分别记为 d 与 d’。我们要证明:

[ \boxed{\forall v,\quad d’(v)\ge d(v).} ]

先观察:增广之后,一条新出现的正残量弧只能是本次所走路径上某条弧的反向弧。若增广路上从 u 走向 v,则它是旧 BFS 的最短路径的一部分,所以 d(v)=d(u)+1。新出现的反向弧 v→u 因而是从旧层 d(v) 指向更低的旧层 d(u),不是向高层的捷径。

更严格地,反设有顶点的距离变小。沿新的最短 s→v 路径,取第一个距离变小的顶点 v,前驱为 u,则 d’(u)≥d(u) 且 d’(v)=d’(u)+1。

若残量弧 u→v 在增广前已存在,旧 BFS 有 d(v)≤d(u)+1≤d’(v),矛盾。若 u→v 是刚新增的反向弧,则原增广路必沿 v→u 走过,故旧层 d(u)=d(v)+1。于是

[ d’(v)=d’(u)+1\ge d(u)+1=d(v)+2, ]

也与“距离下降”矛盾。不存在这种顶点,层数单调性成立。新增反向弧两端本来就在旧增广路上,所以也不会把旧时不可达的顶点突然变为可达。

真正用到的条件是每次选取残量图中的最短边数路径;随便用 DFS 选路,就不能保证上面“新反向弧指向旧低层”的结构。

六、第二个证明:为什么增广至多 O(nm) 次?(约 3 分钟)

一次增广取瓶颈 Δ,因此至少有一条路径弧的残量被减到 0。把这样的弧叫做本轮的关键弧(critical arc)。每次至少有一条关键弧,于是只要限制“同一有向残量弧最多能当多少次关键弧”,就限制了总轮数。

设某轮有向残量弧 u→v 成为关键弧,当时它位于 BFS 最短增广路上,所以

[ d(v)=d(u)+1. ]

它现在残量为 0。若将来同一方向再次成为关键弧,中间必须有人沿反向弧 v→u增广,使 u→v 再次出现正残量。那次使用反向弧时,BFS 路径的层次关系为:

[ d_{\mathrm{later}}(u)=d_{\mathrm{later}}(v)+1 \ge d_{\mathrm{old}}(v)+1 =d_{\mathrm{old}}(u)+2. ]

也就是说,同一有向残量弧两次成为关键弧之间,它的尾点 u 的 BFS 层数至少增加 2。有限的可达层数只有 0,1,…,n−1,因此每条有向残量弧至多成为 O(n) 次关键弧。原始 m 条边最多对应 2m 条配对残量弧,于是:

[ \boxed{\text{增广次数}=O(nm).} ]

每轮 BFS 扫描邻接表和更新增广路,时间 O(n+m)。将无关孤立顶点预先排除或使用时间戳访问标记后,实际扫描工作可按 O(m) 计,于是得到标准的

[ \boxed{T_{\mathrm{EK}}=O(nm^2),\qquad S_{\mathrm{extra}}=O(n+m).} ]

不做上述访问优化时,直接相乘的保守界是 O(nm(n+m));在与源汇相关的连通网络 m=Ω(n) 时它也化为 O(nm²)。特别强调:增广次数的证明完全没有用到 Δ≥1,因此容量即使是非整数,组合上界也成立;这不同于依赖最大流数值 F 的朴素 Ford–Fulkerson。

七、终止证书与边界反例(约 2 分钟)

EK 找不到 s→t 残量路径时,令 S 为残量网络从 s 可达的顶点集。所有原始 S→外部的边必饱和,否则外部顶点也能到达;所有原始外部→S 的边必有零流,否则沿其反向残量弧能到达外部。由流守恒的割净流恒等式:

[ |f|=\sum_{u\in S,v\notin S}f(u,v)-\sum_{u\notin S,v\in S}f(u,v) =\sum_{u\in S,v\notin S}c(u,v)=c(S,V\setminus S). ]

任意可行流的流值都不超过任意 s–t 割容量,所以达到这个上界的 f 是最大流,S 定义的割是最小割。这是与 EK 选路复杂度证明相互独立的最优性证书。

边界和反例要记住四点。第一,BFS 最短边数不等于最大瓶颈:一条两边的窄路径仍可能比三边的宽路径更早被选择。第二,反向残量弧不能删:否则昨天 s→a→b→t 的错误初始分配将无法纠正。第三,零容量弧要跳过;相反方向的真实原边与撤销弧必须分别保存。第四,理论上精确实数容量仍保证有限次增广,但浮点实现要设定一致容差,谨慎处理残量比较和舍入误差,不能把数值近似当成数学上的精确证明。

八、小结与下一课(约 1 分钟)

今天的逻辑链只有三步:

[ \boxed{\text{BFS 最短增广路}\Rightarrow \text{残量距离单调不降}\Rightarrow \text{同一关键弧的层数每次至少增加 2}\Rightarrow O(nm^2).} ]

Ford–Fulkerson 的正确性只依赖“沿残量增广直到无路”;Edmonds–Karp 在这个框架上加入 BFS,进一步给出了与容量数值无关的时间保证。

下一课(2026-11-19,第 31 课):Dinic 的层次图与阻塞流。 比较 EK 每轮只推一条最短增广路,与 Dinic 在同一个 BFS 层次图里连续推送多条路径,直至这一层次的所有 s→t 路径都被阻塞。

九、四级自测(100 分;首次不公布答案)

前 3 题客观判分,最后一题开放证明。课堂只给出答案中立的提示;标准答案、解析与评分细则单独保存在测验 JSON 中。

Lv1|BFS 选路与复杂度机制|15 分|预计 2 分钟|单选

相比允许任意选择残量增广路的 Ford–Fulkerson,Edmonds–Karp 为什么能够给出不依赖最大流数值 F 的增广次数上界?

A. 因为 BFS 每次都找到瓶颈容量最大的增广路。

B. 因为 BFS 每次选残量网络中边数最少的增广路,并可证明残量最短距离不下降、关键弧被反复饱和的次数受限。

C. 因为每次增广都至少让一个原始顶点永久不可达。

D. 因为只要原图的边权非负,所有反向残量弧都可以删除。

中立提示:想一想 BFS 优化的是路径的边数还是瓶颈容量;然后观察某条被饱和的弧再次获得残量需要发生什么。

Lv2|BFS 增广数值 Trace|20 分|预计 4 分钟|单选

网络含 s→a(3)、s→b(2)、a→t(2)、a→b(1)、b→t(3),括号内为容量,初始零流。每轮都用 BFS 找残量网络中边数最少的 s→t 路径;邻接扫描顺序固定为 s 先 a 后 b,a 先 t 后 b,b 先 t。连续完成前三次增广后,(总流值 f , 原始边流量 f(a,b)) 是多少?

A. (4, 1)

B. (5, 0)

C. (5, 1)

D. (4, 0)

中立提示:记录每轮 BFS 发现 t 的最短层数、瓶颈以及每条原边当前流量;第三轮的路径可能比前两轮多一条边。

Lv3|层数单调、非整数容量与反向弧|25 分|预计 4 分钟|多选

对非负容量有向网络,使用精确算术、标准残量弧配对与 BFS 增广的 Edmonds–Karp。下列哪些判断成立?(多选,选出全部正确项)

A. 对增广前后均可达的顶点,源点到它的最短残量路径边数不会下降;不可达可视为距离 +∞。

B. 即使容量不是整数,只要容量是有限非负实数,Edmonds–Karp 仍有 O(nm) 次增广的组合上界。

C. BFS 选择边数最少的增广路,必然也选择瓶颈容量最大的增广路。

D. 由于 BFS 只需找正向原始边上的路径,可以忽略反向残量弧而不影响最大流正确性。

中立提示:将“层数单调”“容量是否为整数”“最少边数与最大瓶颈是不是同一目标”“反向边能否重排已有流量”分别检查。

Lv4|层数证明、关键弧计数与最小割证书|40 分|预计 12 分钟|开放推导

给定 n≥2 个顶点、m≥1 条有向边、容量为有限非负实数的网络,源 s、汇 t。(a)(10 分)写出 Edmonds–Karp 的 BFS 增广伪代码,包含正反残量弧、瓶颈和流值更新。(b)(12 分)定义每轮残量图从 s 的最短边数距离 d(v),证明每次增广后距离不下降,并解释新增反向弧为何不会产生更短路径。(c)(10 分)定义一条在增广中被饱和的“关键弧”,说明同一有向残量弧两次成为关键弧之间,其尾点层数为何至少增加 2;据此推出 O(nm) 次增广和标准 O(nm²) 时间界,并说明它为什么不依赖容量数值。(d)(8 分)证明停止时由残量可达点集 S 构造的割满足流值等于该割容量,以及在实现中零容量边、反向原始边和浮点误差分别应如何处理。

中立提示:用“旧残量图里可达的最短层数”跟踪新增反向弧;一条弧再次具有正残量,必须有人沿它的反向弧增广。终止证明则检查割两侧原始边的饱和与零回流。

十、提交与反馈

回复 Lv1:选项;Lv2:选项及三轮流量;Lv3:全部正确选项;Lv4:(a)–(d) 的完整推导。我会按 15/20/25/40 分逐题批改:80–100 分按课表进入 Dinic;60–79 分补 BFS 层次或关键弧证明;低于 60 分先重做残量网络及最大流–最小割证书。补练不改变自然日课号。