xxx 最大流问题（Edmonds-Karp 算法）
字数 2484 2025-12-04 05:41:27

xxx 最大流问题（Edmonds-Karp 算法）

我将为你讲解最大流问题中的 Edmonds-Karp 算法。这是一个经典算法，用于解决网络流中的最大流问题。

问题描述

最大流问题是指在一个有向图中，每条边都有一个容量（表示该边能承载的最大流量），我们需要找到从源点（s）到汇点（t）的最大流量。流量必须满足两个条件：

  1. 容量约束：每条边上的流量不能超过其容量。
  2. 流量守恒：除了源点和汇点，流入每个顶点的总流量等于流出该顶点的总流量。

解题过程

Edmonds-Karp 算法是 Ford-Fulkerson 方法的一种具体实现，其核心思想是不断在残量图中寻找增广路径，并沿该路径增加流量，直到找不到增广路径为止。它的关键特点在于使用广度优先搜索（BFS）来寻找增广路径，这保证了路径是最短路径（按边数计算）。

步骤 1：理解残量图

残量图是算法的基础。对于原图中的每条边 (u, v) 及其容量 c(u, v) 和当前流量 f(u, v)，我们在残量图中创建两条边：

  1. 前向边：从 u 到 v，残量容量为 c(u, v) - f(u, v)。这表示还可以增加多少流量。
  2. 反向边：从 v 到 u，残量容量为 f(u, v)。这表示可以“退回”多少流量（即减少正向流量）。

初始时，所有流量为 0，所以前向边的残量容量等于原始容量，反向边的残量容量为 0。

步骤 2：算法框架

算法的主循环如下：

  1. 在残量图上，使用 BFS 从源点 s 开始，寻找一条到达汇点 t 的路径。这条路径上的每条边的残量容量都必须大于 0。
  2. 如果存在这样的路径（称为增广路径），则找到该路径上所有边的最小残量容量。这个值就是该路径可以增加的流量值，记作 min_cap。
  3. 沿着这条增广路径，更新残量图：
    • 对于路径上的每条前向边 (u, v)，减少其残量容量 min_cap（相当于增加流量）。
    • 对于对应的反向边 (v, u)，增加其残量容量 min_cap（相当于为可能的流量退回提供空间）。
  4. 将 min_cap 加到总流量中。
  5. 重复步骤 1-4，直到 BFS 无法找到从 s 到 t 的路径为止。此时，总流量即为最大流。

步骤 3：详细示例

考虑一个简单网络：源点 s，汇点 t，中间顶点 A 和 B。
边及其容量为：

  • s -> A: 3
  • s -> B: 2
  • A -> B: 2
  • A -> t: 1
  • B -> t: 3

迭代 1：

  1. BFS 在残量图中找到路径 s -> A -> t。路径上的最小残量容量是 min(3, 1) = 1。
  2. 沿路径增加流量 1。
  3. 更新残量图：
    • 边 s->A 容量变为 3-1=2。
    • 边 A->t 容量变为 1-1=0。
    • 同时，创建/更新反向边 A->s 容量为 1， t->A 容量为 1。
      总流量 = 1。

迭代 2：

  1. BFS 找到另一条路径 s -> B -> t。最小残量容量 min(2, 3) = 2。
  2. 增加流量 2。
  3. 更新残量图：
    • s->B: 2-2=0
    • B->t: 3-2=1
    • 反向边 B->s: 2, t->B: 2
      总流量 = 1+2=3。

迭代 3：

  1. BFS 找到路径 s -> A -> B -> t。注意，虽然 A->t 已经饱和（容量为0），但 A->B 的容量为2，B->t 的容量为1（来自上一步更新）。路径 s-A-B-t 上最小残量容量为 min(s->A:2, A->B:2, B->t:1) = 1。
  2. 增加流量 1。
  3. 更新残量图：
    • s->A: 2-1=1
    • A->B: 2-1=1
    • B->t: 1-1=0
    • 同时更新反向边。
      总流量 = 3+1=4。

迭代 4：

  1. 再次进行 BFS。从 s 出发，可以到达 A（s->A 容量1），从 A 出发，边 A->t 容量为0，A->B 容量为1（前向边）。通过 A->B 到达 B。从 B 出发，B->t 容量为0。但是，检查反向边！B->A 的容量是多少？在第一次迭代中，我们流过 A->t，创建了反向边 t->A。在第三次迭代中，我们流过了 A->B，这创建了反向边 B->A，其容量为1（等于第三次迭代中流过 A->B 的流量）。
    • 因此，从 B 可以通过反向边 B->A 回到 A。这相当于“退回”一部分从 A 流向 B 的流量。
    • 从 A 再通过反向边 A->s？不行，A->s 是反向边，但它是流入 s 的，在 BFS 中我们不会走回源点。那么从 A 还能去哪？A->t 容量0，A->B 容量1（但刚从B来）。所以这条路不通。
      实际上，正确的增广路径是 s -> B -> A -> t。
    • s->B 容量为0？不，在第二次迭代中 s->B 已经饱和（容量0）。所以从 s 无法直接到 B。
      那么从 s 出发，只能到 A（s->A 容量1）。从 A 可以到 B（A->B 容量1）。从 B 可以到 t？B->t 容量0。从 B 可以到 A 吗？通过反向边 B->A？是的，B->A 的容量是1（由第三次迭代产生）。从 A 可以到 t？A->t 容量0。此路不通。
      最终，BFS 找不到任何从 s 到 t 的路径。算法终止。

最终总最大流为 4。

步骤 4：算法特性

  • 时间复杂度：O(V * E²)，其中 V 是顶点数，E 是边数。因为 BFS 的时间是 O(E)，而最多可能进行 O(V * E) 次增广。
  • 为什么使用 BFS：BFS 总是找到最短的增广路径（边数最少）。这避免了 Ford-Fulkerson 方法在某些情况下因选择不良路径而导致的糟糕性能（特别是当边容量是无理数时），保证了算法在多项式时间内结束。
  • 反向边的作用：反向边允许算法“撤销”先前做出的流分配决策，从而找到更优的全局流量分配方案。这是最大流算法的核心思想之一。

总结

Edmonds-Karp 算法通过不断在残量图中寻找最短增广路径并增加流量，最终求得最大流。其 BFS 策略保证了效率和正确性，而反向边的引入使得流量重新分配成为可能，是理解许多更复杂网络流算法的基础。

xxx 最大流问题（Edmonds-Karp 算法） 我将为你讲解最大流问题中的 Edmonds-Karp 算法。这是一个经典算法，用于解决网络流中的最大流问题。 问题描述 最大流问题是指在一个有向图中，每条边都有一个容量（表示该边能承载的最大流量），我们需要找到从源点（s）到汇点（t）的最大流量。流量必须满足两个条件： 容量约束：每条边上的流量不能超过其容量。 流量守恒：除了源点和汇点，流入每个顶点的总流量等于流出该顶点的总流量。 解题过程 Edmonds-Karp 算法是 Ford-Fulkerson 方法的一种具体实现，其核心思想是不断在残量图中寻找增广路径，并沿该路径增加流量，直到找不到增广路径为止。它的关键特点在于使用广度优先搜索（BFS）来寻找增广路径，这保证了路径是最短路径（按边数计算）。 步骤 1：理解残量图 残量图是算法的基础。对于原图中的每条边 (u, v) 及其容量 c(u, v) 和当前流量 f(u, v)，我们在残量图中创建两条边： 前向边：从 u 到 v，残量容量为 c(u, v) - f(u, v)。这表示还可以增加多少流量。 反向边：从 v 到 u，残量容量为 f(u, v)。这表示可以“退回”多少流量（即减少正向流量）。 初始时，所有流量为 0，所以前向边的残量容量等于原始容量，反向边的残量容量为 0。 步骤 2：算法框架 算法的主循环如下： 在残量图上，使用 BFS 从源点 s 开始，寻找一条到达汇点 t 的路径。这条路径上的每条边的残量容量都必须大于 0。 如果存在这样的路径（称为增广路径），则找到该路径上所有边的最小残量容量。这个值就是该路径可以增加的流量值，记作 min_cap 。 沿着这条增广路径，更新残量图： 对于路径上的每条前向边 (u, v)，减少其残量容量 min_cap （相当于增加流量）。 对于对应的反向边 (v, u)，增加其残量容量 min_cap （相当于为可能的流量退回提供空间）。 将 min_cap 加到总流量中。 重复步骤 1-4，直到 BFS 无法找到从 s 到 t 的路径为止。此时，总流量即为最大流。 步骤 3：详细示例 考虑一个简单网络：源点 s，汇点 t，中间顶点 A 和 B。 边及其容量为： s -> A: 3 s -> B: 2 A -> B: 2 A -> t: 1 B -> t: 3 迭代 1： BFS 在残量图中找到路径 s -> A -> t。路径上的最小残量容量是 min(3, 1) = 1。 沿路径增加流量 1。 更新残量图： 边 s->A 容量变为 3-1=2。 边 A->t 容量变为 1-1=0。 同时，创建/更新反向边 A->s 容量为 1， t->A 容量为 1。 总流量 = 1。 迭代 2： BFS 找到另一条路径 s -> B -> t。最小残量容量 min(2, 3) = 2。 增加流量 2。 更新残量图： s->B: 2-2=0 B->t: 3-2=1 反向边 B->s: 2, t->B: 2 总流量 = 1+2=3。 迭代 3： BFS 找到路径 s -> A -> B -> t。注意，虽然 A->t 已经饱和（容量为0），但 A->B 的容量为2，B->t 的容量为1（来自上一步更新）。路径 s-A-B-t 上最小残量容量为 min(s->A:2, A->B:2, B->t:1) = 1。 增加流量 1。 更新残量图： s->A: 2-1=1 A->B: 2-1=1 B->t: 1-1=0 同时更新反向边。 总流量 = 3+1=4。 迭代 4： 再次进行 BFS。从 s 出发，可以到达 A（s->A 容量1），从 A 出发，边 A->t 容量为0，A->B 容量为1（前向边）。通过 A->B 到达 B。从 B 出发，B->t 容量为0。但是，检查反向边！B->A 的容量是多少？在第一次迭代中，我们流过 A->t，创建了反向边 t->A。在第三次迭代中，我们流过了 A->B，这创建了反向边 B->A，其容量为1（等于第三次迭代中流过 A->B 的流量）。 因此，从 B 可以通过反向边 B->A 回到 A。这相当于“退回”一部分从 A 流向 B 的流量。 从 A 再通过反向边 A->s？不行，A->s 是反向边，但它是流入 s 的，在 BFS 中我们不会走回源点。那么从 A 还能去哪？A->t 容量0，A->B 容量1（但刚从B来）。所以这条路不通。 实际上，正确的增广路径是 s -> B -> A -> t。 s->B 容量为0？不，在第二次迭代中 s->B 已经饱和（容量0）。所以从 s 无法直接到 B。 那么从 s 出发，只能到 A（s->A 容量1）。从 A 可以到 B（A->B 容量1）。从 B 可以到 t？B->t 容量0。从 B 可以到 A 吗？通过反向边 B->A？是的，B->A 的容量是1（由第三次迭代产生）。从 A 可以到 t？A->t 容量0。此路不通。 最终，BFS 找不到任何从 s 到 t 的路径。算法终止。 最终总最大流为 4。 步骤 4：算法特性 时间复杂度 ：O(V * E²)，其中 V 是顶点数，E 是边数。因为 BFS 的时间是 O(E)，而最多可能进行 O(V * E) 次增广。 为什么使用 BFS ：BFS 总是找到最短的增广路径（边数最少）。这避免了 Ford-Fulkerson 方法在某些情况下因选择不良路径而导致的糟糕性能（特别是当边容量是无理数时），保证了算法在多项式时间内结束。 反向边的作用 ：反向边允许算法“撤销”先前做出的流分配决策，从而找到更优的全局流量分配方案。这是最大流算法的核心思想之一。 总结 Edmonds-Karp 算法通过不断在残量图中寻找最短增广路径并增加流量，最终求得最大流。其 BFS 策略保证了效率和正确性，而反向边的引入使得流量重新分配成为可能，是理解许多更复杂网络流算法的基础。