算法简介
Edmonds-Karp算法是Ford-Fulkerson方法的一种具体实现，其核心改进在于每次寻找增广路时使用BFS（广度优先搜索）而非DFS，从而保证了算法的时间复杂度上界。该算法用于求解网络流问题中的最大流：给定一个有向图，每条边有容量限制，求从源点到汇点能传输的最大流量。
核心思想
最大流问题的核心是残量网络（Residual Network）的概念：
- 残量容量：对于每条边 $(u, v)$，残量容量 $r(u, v) = c(u, v) – f(u, v)$，表示该边还能增加的流量
- 反向边：为了允许”撤销”之前的流量分配，引入反向边，其残量容量 $r(v, u) = f(u, v)$
- 增广路：残量网络中从源点到汇点的一条路径，路径上所有边的残量容量都大于0
- 瓶颈容量：增广路上最小的残量容量，即本次增广能增加的最大流量
Edmonds-Karp算法不断使用BFS在残量网络中寻找最短增广路，直到不存在增广路为止，此时得到的流即为最大流。
Java实现
import java.util.*;
/**
* Edmonds-Karp最大流算法实现
* 使用BFS在残量网络中寻找最短增广路
*
* @author AlgorithmDaily
*/
public class EdmondsKarp {
private int n; // 顶点数量
private int source; // 源点
private int sink; // 汇点
private int[][] capacity; // 容量矩阵
private int[][] flow; // 流量矩阵
private int[] parent; // BFS记录父节点
public EdmondsKarp(int n, int source, int sink) {
this.n = n;
this.source = source;
this.sink = sink;
this.capacity = new int[n][n];
this.flow = new int[n][n];
this.parent = new int[n];
}
/**
* 添加边及其容量
* @param u 起点
* @param v 终点
* @param cap 容量
*/
public void addEdge(int u, int v, int cap) {
capacity[u][v] += cap; // 支持重边
}
/**
* 使用BFS在残量网络中寻找从源点到汇点的最短增广路
* @return 增广路的瓶颈容量，如果不存在则返回0
*/
private int bfs() {
Arrays.fill(parent, -1);
parent[source] = source;
// 队列中存储顶点，同时记录到达该顶点的残量容量
Queue<int[]> queue = new LinkedList<>();
queue.offer(new int[]{source, Integer.MAX_VALUE});
while (!queue.isEmpty()) {
int[] curr = queue.poll();
int u = curr[0];
int currFlow = curr[1];
for (int v = 0; v < n; v++) {
// parent[v] == -1 表示未访问，且残量容量大于0
if (parent[v] == -1 && capacity[u][v] - flow[u][v] > 0) {
parent[v] = u;
int newFlow = Math.min(currFlow, capacity[u][v] - flow[u][v]);
if (v == sink) {
return newFlow; // 找到汇点，返回瓶颈容量
}
queue.offer(new int[]{v, newFlow});
}
}
}
return 0; // 不存在增广路
}
/**
* 执行Edmonds-Karp算法计算最大流
* @return 从源点到汇点的最大流量
*/
public int maxFlow() {
int totalFlow = 0;
int augmentFlow;
// 循环直到不存在增广路
while ((augmentFlow = bfs()) > 0) {
totalFlow += augmentFlow;
// 回溯更新流量矩阵
int v = sink;
while (v != source) {
int u = parent[v];
flow[u][v] += augmentFlow; // 正向边增加流量
flow[v][u] -= augmentFlow; // 反向边减少流量（增加残量）
v = u;
}
}
return totalFlow;
}
/**
* 获取最小割的S集合（源点一侧的顶点）
*/
public List<Integer> getMinCutS() {
boolean[] visited = new boolean[n];
Queue<Integer> queue = new LinkedList<>();
queue.offer(source);
visited[source] = true;
while (!queue.isEmpty()) {
int u = queue.poll();
for (int v = 0; v < n; v++) {
if (!visited[v] && capacity[u][v] - flow[u][v] > 0) {
visited[v] = true;
queue.offer(v);
}
}
}
List<Integer> sSet = new ArrayList<>();
for (int i = 0; i < n; i++) {
if (visited[i]) sSet.add(i);
}
return sSet;
}
/**
* 打印当前流量分配情况
*/
public void printFlow() {
System.out.println("=== 流量分配 ===");
for (int u = 0; u < n; u++) {
for (int v = 0; v < n; v++) {
if (flow[u][v] > 0) {
System.out.printf(" %d -> %d: %d / %d%n",
u, v, flow[u][v], capacity[u][v]);
}
}
}
}
/**
* 主程序：演示Edmonds-Karp算法
*/
public static void main(String[] args) {
// 构建测试网络（经典示例）
// 0(源点)
// / | \
// 1 2 3
// /\ | /\
// 4 5-6 7
// \ | / /
// \ | / /
// 8(汇点)
EdmondsKarp ek = new EdmondsKarp(9, 0, 8);
// 从源点出发的边
ek.addEdge(0, 1, 10);
ek.addEdge(0, 2, 10);
ek.addEdge(0, 3, 10);
// 中间层边
ek.addEdge(1, 4, 5);
ek.addEdge(1, 5, 5);
ek.addEdge(2, 5, 10);
ek.addEdge(3, 6, 5);
ek.addEdge(3, 7, 5);
// 交叉边
ek.addEdge(5, 6, 10);
// 到汇点的边
ek.addEdge(4, 8, 5);
ek.addEdge(5, 8, 10);
ek.addEdge(6, 8, 5);
ek.addEdge(7, 8, 5);
int maxFlow = ek.maxFlow();
System.out.println("=== Edmonds-Karp最大流 ===");
System.out.println("最大流量: " + maxFlow);
ek.printFlow();
System.out.println("\n最小割S集合: " + ek.getMinCutS());
// 验证：根据最大流最小割定理，最大流等于最小割容量
System.out.println("\n验证：最大流 = " + maxFlow + "，应等于最小割容量");
}
}
复杂度分析
- 时间复杂度：$O(V \cdot E^2)$，其中 $V$ 是顶点数，$E$ 是边数。每次BFS的时间复杂度为 $O(E)$，而增广次数最多为 $O(V \cdot E)$。
- 空间复杂度：$O(V^2)$，使用邻接矩阵存储容量和流量。若使用邻接表可优化到 $O(V + E)$。
算法特点与适用场景
优点：
– 时间复杂度有确定上界，相比Ford-Fulkerson的DFS实现更加稳定
– 实现简单，BFS天然保证了找到的是最短增广路
– 基于最大流最小割定理，算法正确性有严格证明
缺点：
– 时间复杂度不如Dinic算法（$O(V^2 \cdot E)$ 或 $O(E \cdot \sqrt{V})$）
– 对于单位容量网络仍有优化空间
适用场景：网络路由优化、二分图最大匹配、任务分配、图像分割中的图割算法等。
