每日算法 — 使用java实现Edmonds-Karp最大流：BFS增广路与网络流优化

引言

网络流问题是图论与运筹学中的经典课题，广泛应用于交通调度、资源分配、图像分割等领域。Edmonds-Karp算法是Ford-Fulkerson方法的一个具体实现，其核心改进在于使用BFS来寻找最短增广路（按边数最少），从而将时间复杂度从指数级优化到多项式级O(VE²)。本文将用Java完整实现该算法，并深入讲解最大流最小割定理的工程意义。

算法原理

残量网络

对于流网络中的每条边(u, v)，定义残量容量为：

• 正向边残量：c_f(u, v) = c(u, v) – f(u, v)
• 反向边残量：c_f(v, u) = f(u, v)

其中c为容量，f为当前流量。反向边的存在使得算法可以”撤销”之前的不优决策，这是网络流算法的关键设计。

增广路

增广路是指在残量网络中从源点s到汇点t的一条路径，路径上所有边的残量容量均为正。增广路的流量增加量等于路径上最小残量容量。

Edmonds-Karp核心流程

1. 初始化所有边流量为0
2. 在残量网络中用BFS寻找s到t的最短增广路
3. 若不存在增广路，算法终止
4. 否则沿增广路增加流量，更新残量网络
5. 重复步骤2-4

最大流最小割定理

网络的最大流值等于最小割的容量。最小割是将顶点集划分为包含s的集合S和包含t的集合T后，从S到T的所有边容量之和的最小值。

Java完整实现

import java.util.*;

/**
 * Edmonds-Karp最大流算法实现
 * 基于BFS寻找最短增广路，时间复杂度O(V * E^2)
 */
public class EdmondsKarpMaxFlow {

    // 边的内部类，支持正向边和反向边
    static class Edge {
        int from, to;      // 起点和终点
        int capacity;      // 容量
        int flow;          // 当前流量
        Edge reverse;      // 反向边引用

        Edge(int from, int to, int capacity) {
            this.from = from;
            this.to = to;
            this.capacity = capacity;
            this.flow = 0;
        }

        // 返回残量容量
        int residualCapacity() {
            return capacity - flow;
        }
    }

    private final int n;                    // 顶点数量
    private final List<Edge>[] graph;       // 邻接表
    private final int source;               // 源点
    private final int sink;                 // 汇点

    @SuppressWarnings("unchecked")
    public EdmondsKarpMaxFlow(int n, int source, int sink) {
        this.n = n;
        this.source = source;
        this.sink = sink;
        this.graph = new ArrayList[n];
        for (int i = 0; i < n; i++) {
            graph[i] = new ArrayList<>();
        }
    }

    /**
     * 添加一条有向边，同时创建反向边
     * @param from 起点
     * @param to 终点
     * @param capacity 容量
     */
    public void addEdge(int from, int to, int capacity) {
        Edge forward = new Edge(from, to, capacity);
        Edge backward = new Edge(to, from, 0);  // 反向边初始容量为0
        forward.reverse = backward;
        backward.reverse = forward;
        graph[from].add(forward);
        graph[to].add(backward);
    }

    /**
     * 执行Edmonds-Karp算法计算最大流
     * @return 从源点到汇点的最大流量
     */
    public int maxFlow() {
        int totalFlow = 0;
        int[] parent = new int[n];      // BFS中记录每个点的前驱边索引
        Edge[] parentEdge = new Edge[n]; // 记录前驱边对象

        // 不断寻找增广路直到不存在
        while (bfs(parent, parentEdge)) {
            // 从汇点回溯到源点，找到增广路上的最小残量
            int pathFlow = Integer.MAX_VALUE;
            for (int v = sink; v != source; v = parentEdge[v].from) {
                pathFlow = Math.min(pathFlow, parentEdge[v].residualCapacity());
            }

            // 沿增广路更新流量
            for (int v = sink; v != source; v = parentEdge[v].from) {
                Edge e = parentEdge[v];
                e.flow += pathFlow;           // 正向边增加流量
                e.reverse.flow -= pathFlow;   // 反向边减少流量（允许撤销）
            }

            totalFlow += pathFlow;
        }

        return totalFlow;
    }

    /**
     * BFS寻找从源点到汇点的最短增广路
     * @param parent 记录前驱顶点
     * @param parentEdge 记录前驱边
     * @return 是否存在增广路
     */
    private boolean bfs(int[] parent, Edge[] parentEdge) {
        Arrays.fill(parent, -1);
        Arrays.fill(parentEdge, null);
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);
        parent[source] = source;

        while (!queue.isEmpty()) {
            int u = queue.poll();

            // 遍历u的所有邻接边
            for (Edge e : graph[u]) {
                int v = e.to;
                // 只考虑残量容量大于0的边，且未访问过的顶点
                if (parent[v] == -1 && e.residualCapacity() > 0) {
                    parent[v] = u;
                    parentEdge[v] = e;
                    queue.offer(v);

                    // 提前终止：找到汇点即可返回
                    if (v == sink) {
                        return true;
                    }
                }
            }
        }

        return false;
    }

    /**
     * 获取最小割的S集合（最大流后从源点可达的顶点）
     * @return 最小割S侧的顶点集合
     */
    public Set<Integer> minCutS() {
        Set<Integer> reachable = new HashSet<>();
        boolean[] visited = new boolean[n];
        Queue<Integer> queue = new LinkedList<>();
        queue.offer(source);
        visited[source] = true;
        reachable.add(source);

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (Edge e : graph[u]) {
                if (!visited[e.to] && e.residualCapacity() > 0) {
                    visited[e.to] = true;
                    reachable.add(e.to);
                    queue.offer(e.to);
                }
            }
        }
        return reachable;
    }

    /**
     * 打印当前网络的流量状态
     */
    public void printFlow() {
        System.out.println("网络流量状态：");
        for (int u = 0; u < n; u++) {
            for (Edge e : graph[u]) {
                // 只打印原始正向边（避免重复打印反向边）
                if (e.capacity > 0) {
                    System.out.printf("  边 %d -> %d: %d / %d%n",
                            e.from, e.to, e.flow, e.capacity);
                }
            }
        }
    }

    public static void main(String[] args) {
        // 经典测试案例：从0到5的最大流
        // 参考CLRS教材中的流网络示例
        EdmondsKarpMaxFlow maxFlow = new EdmondsKarpMaxFlow(6, 0, 5);

        maxFlow.addEdge(0, 1, 16);
        maxFlow.addEdge(0, 2, 13);
        maxFlow.addEdge(1, 2, 10);
        maxFlow.addEdge(1, 3, 12);
        maxFlow.addEdge(2, 1, 4);
        maxFlow.addEdge(2, 4, 14);
        maxFlow.addEdge(3, 2, 9);
        maxFlow.addEdge(3, 5, 20);
        maxFlow.addEdge(4, 3, 7);
        maxFlow.addEdge(4, 5, 4);

        int result = maxFlow.maxFlow();
        System.out.println("最大流值: " + result);  // 期望输出: 23

        maxFlow.printFlow();

        Set<Integer> minCut = maxFlow.minCutS();
        System.out.println("最小割S集合: " + minCut);
    }
}

复杂度分析

Edmonds-Karp的时间复杂度分析基于一个关键性质：每条边作为瓶颈边的次数最多为O(V)。因为每次增广后，该边在残量网络中的距离至少增加2，而距离上限为V。

应用场景

• 二分图最大匹配：将源点连左侧顶点，右侧顶点连汇点，边容量为1
• 多源多汇问题：添加超级源点和超级汇点
• 带下界网络流：通过差分约束转化为标准最大流
• 最小割问题：直接利用最大流最小割定理求解

总结

Edmonds-Karp算法通过BFS寻找最短增广路，巧妙地规避了一般Ford-Fulkerson方法的最坏情况，是学习和理解网络流问题的最佳入门算法。其核心设计——残量网络与反向边——不仅是该算法的基础，也是Dinic、ISAP等更高级网络流算法的基石。掌握Edmonds-Karp后，读者可以进一步学习时间复杂度为O(E√V)的Dinic算法，以应对更大规模的网络流问题。