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

Edmonds-Karp 算法

Edmonds-Karp 算法

Edmonds-Karp 是 Ford-Fulkerson 方法的确定化版本:每轮都用 BFS 选择边数最少的增广路径。本课将实现基于邻接表的残量网络,并从距离单调性解释其多项式复杂度。

学习目标

  • 使用 BFS 在残量网络中寻找最短增广路径。
  • 正确维护成对的正向边与反向边。
  • 理解 O(VE2)O(VE^2) 时间复杂度的来源及适用前提。

核心原理

Edmonds-Karp 与 Ford-Fulkerson 的流量更新规则完全相同,区别只在路径选择:BFS 按边数分层搜索,因此总是优先得到从源点到汇点的最短增广路径。顶点第一次入队时就记录父边,可以避免重复入队并恢复完整路径。

Edmonds-Karp BFS 分层增广过程

多项式复杂度来源

一次 BFS 使用邻接表扫描残量边,成本为 O(E)O(E)。某条边成为最短增广路径上的瓶颈并被饱和后,如果它以后再次成为同方向的瓶颈,源点到该边起点的 BFS 距离至少增加 2。距离最多增长到 V−1V - 1,因此每条边成为关键瓶颈的次数是 O(V)O(V),总增广次数为 O(VE)O(VE),最终时间复杂度为 O(VE2)O(VE^2)。

该上界不依赖最大流数值,所以即使容量很大,也不会像普通 DFS 版本那样按流量单位反复增广。若改用邻接矩阵,单次 BFS 可能扫描 V2V^2 个位置,代码仍正确,但不再直接体现邻接表下的理论界。

实现边界与常见错误

  • BFS 只能沿 residualCapacity > 0 的边前进。
  • 每条输入边必须配一条初始容量为 0 的反向边,并保存彼此在邻接表中的下标。
  • 顶点应在入队时标记访问,否则同一顶点可能被多个前驱重复加入队列。
  • 使用浮点容量时要设置容差,否则极小残量可能造成无意义的重复搜索;整数容量最容易验证。

完整可运行示例

下面的 Java 17 程序用 Edge 对象保存终点、反向边下标和当前残量。BFS 记录父顶点与父边,找到汇点后回溯计算瓶颈并更新一对残量边。

java
import java.util.ArrayDeque;
import java.util.ArrayList;
import java.util.Arrays;
import java.util.Collections;
import java.util.List;
import java.util.Queue;

public class EdmondsKarpDemo {

    static final class Edge {
        final int to;
        final int reverseIndex;
        int residualCapacity;

        Edge(int to, int reverseIndex, int residualCapacity) {
            this.to = to;
            this.reverseIndex = reverseIndex;
            this.residualCapacity = residualCapacity;
        }
    }

    static final class FlowNetwork {
        private final List<Edge>[] graph;

        @SuppressWarnings("unchecked")
        FlowNetwork(int vertexCount) {
            graph = new List[vertexCount];
            for (int i = 0; i < vertexCount; i++) {
                graph[i] = new ArrayList<>();
            }
        }

        void addEdge(int from, int to, int capacity) {
            Edge forward = new Edge(to, graph[to].size(), capacity);
            Edge reverse = new Edge(from, graph[from].size(), 0);
            graph[from].add(forward);
            graph[to].add(reverse);
        }

        int edmondsKarp(int source, int sink) {
            int[] parentVertex = new int[graph.length];
            Edge[] parentEdge = new Edge[graph.length];
            int maxFlow = 0;

            while (bfs(source, sink, parentVertex, parentEdge)) {
                int bottleneck = Integer.MAX_VALUE;
                for (int v = sink; v != source; v = parentVertex[v]) {
                    bottleneck = Math.min(
                            bottleneck, parentEdge[v].residualCapacity);
                }

                for (int v = sink; v != source; v = parentVertex[v]) {
                    Edge edge = parentEdge[v];
                    edge.residualCapacity -= bottleneck;
                    graph[edge.to].get(edge.reverseIndex).residualCapacity += bottleneck;
                }

                maxFlow += bottleneck;
                System.out.println(
                        "增广路径: " + buildPath(source, sink, parentVertex)
                                + ", 流量: " + bottleneck);
            }

            return maxFlow;
        }

        private boolean bfs(
                int source, int sink, int[] parentVertex, Edge[] parentEdge) {
            Arrays.fill(parentVertex, -1);
            Arrays.fill(parentEdge, null);
            Queue<Integer> queue = new ArrayDeque<>();
            queue.offer(source);
            parentVertex[source] = source;

            while (!queue.isEmpty()) {
                int u = queue.poll();
                for (Edge edge : graph[u]) {
                    if (edge.residualCapacity > 0
                            && parentVertex[edge.to] == -1) {
                        parentVertex[edge.to] = u;
                        parentEdge[edge.to] = edge;
                        if (edge.to == sink) {
                            return true;
                        }
                        queue.offer(edge.to);
                    }
                }
            }

            return false;
        }

        private String buildPath(
                int source, int sink, int[] parentVertex) {
            List<Integer> path = new ArrayList<>();
            for (int v = sink; v != source; v = parentVertex[v]) {
                path.add(v);
            }
            path.add(source);
            Collections.reverse(path);

            StringBuilder result = new StringBuilder();
            for (int i = 0; i < path.size(); i++) {
                if (i > 0) {
                    result.append(" -> ");
                }
                result.append(path.get(i));
            }
            return result.toString();
        }
    }

    public static void main(String[] args) {
        FlowNetwork network = new FlowNetwork(4);
        network.addEdge(0, 1, 3);
        network.addEdge(0, 2, 2);
        network.addEdge(1, 2, 1);
        network.addEdge(1, 3, 2);
        network.addEdge(2, 3, 3);

        int maxFlow = network.edmondsKarp(0, 3);
        System.out.println("最大流: " + maxFlow);
    }
}

运行命令如下:

bash
javac EdmondsKarpDemo.java
java EdmondsKarpDemo

预期输出

text
增广路径: 0 -> 1 -> 3, 流量: 2
增广路径: 0 -> 2 -> 3, 流量: 2
增广路径: 0 -> 1 -> 2 -> 3, 流量: 1
最大流: 5

前两轮优先选择两条长度为 2 的路径,第三轮才使用长度为 3 的路径。这个顺序体现了 BFS 的最短边数策略,而不是按瓶颈大小排序。

练习

  1. 为 bfs 增加层级数组并打印每轮汇点层级,验收条件是层级序列不下降。
  2. 新增一条容量为 1 的边 0 -> 3,预测第一轮路径和最终最大流,再运行程序核对。

本课总结

  • Edmonds-Karp 用 BFS 约束增广路径选择,使最短路径层级具有单调性。
  • 邻接表下每次 BFS 为 O(E)O(E),总复杂度为 O(VE2)O(VE^2),与容量数值大小无关。
  • 正反向边的成对维护是残量网络实现正确性的核心。

下一课预告

下一阶段将继续研究更高效的分层增广思路,并把最大流模型应用到二分图匹配、最小割和实际资源分配问题中。

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

目录与阅读设置

阅读设置

17

记录一个想法

Edmonds-Karp 算法

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

登录哪都通