Java实现最大流算法详解（从零开始掌握Ford-Fulkerson方法）

Ford-Fulkerson 算法原理

Ford-Fulkerson算法 是解决最大流问题的经典方法。其核心思想是：

1. 从源点到汇点找一条“增广路径”（即还能增加流量的路径）；
2. 沿着这条路径尽可能多地推送流量（受限于路径上最小容量）；
3. 更新图中各边的剩余容量；
4. 重复上述过程，直到找不到增广路径为止。

为了高效查找增广路径，通常使用 DFS（深度优先搜索）或 BFS（广度优先搜索）。使用 BFS 的版本被称为 Edmonds-Karp 算法，它能保证多项式时间复杂度。

用 Java 实现最大流算法

下面我们用 Java 编写一个完整的最大流求解器。我们将使用邻接矩阵表示图，并采用 BFS 查找增广路径（即 Edmonds-Karp 实现）。

import java.util.*;public class MaxFlow {    private static final int INF = Integer.MAX_VALUE;    public static int fordFulkerson(int[][] graph, int source, int sink) {        int n = graph.length;        int[][] residualGraph = new int[n][n];        // 初始化残量图        for (int i = 0; i < n; i++) {            for (int j = 0; j < n; j++) {                residualGraph[i][j] = graph[i][j];            }        }        int maxFlow = 0;        int[] parent = new int[n];        // 不断寻找增广路径        while (bfs(residualGraph, source, sink, parent)) {            // 找到路径上的最小残量            int pathFlow = INF;            for (int v = sink; v != source; v = parent[v]) {                int u = parent[v];                pathFlow = Math.min(pathFlow, residualGraph[u][v]);            }            // 更新残量图            for (int v = sink; v != source; v = parent[v]) {                int u = parent[v];                residualGraph[u][v] -= pathFlow;                residualGraph[v][u] += pathFlow; // 反向边            }            maxFlow += pathFlow;        }        return maxFlow;    }    // 使用BFS查找增广路径    private static boolean bfs(int[][] graph, int source, int sink, int[] parent) {        int n = graph.length;        boolean[] visited = new boolean[n];        Queue<Integer> queue = new LinkedList<>();        queue.offer(source);        visited[source] = true;        parent[source] = -1;        while (!queue.isEmpty()) {            int u = queue.poll();            for (int v = 0; v < n; v++) {                if (!visited[v] && graph[u][v] > 0) {                    queue.offer(v);                    parent[v] = u;                    visited[v] = true;                }            }        }        return visited[sink];    }    // 测试示例    public static void main(String[] args) {        // 图的邻接矩阵表示（0 表示无边）        int[][] graph = {            {0, 16, 13, 0, 0, 0},            {0, 0, 10, 12, 0, 0},            {0, 4, 0, 0, 14, 0},            {0, 0, 9, 0, 0, 20},            {0, 0, 0, 7, 0, 4},            {0, 0, 0, 0, 0, 0}        };        int source = 0, sink = 5;        System.out.println("最大流为: " + fordFulkerson(graph, source, sink));        // 输出: 最大流为: 23    }}

代码说明

• 残量图（Residual Graph）：用于记录每条边当前还能承载多少流量，以及反向边（允许“撤销”流量）；
• BFS 函数：负责查找是否存在从源点到汇点的路径；
• 路径流量（pathFlow）：取路径上所有边的最小残量；
• 更新操作：正向边减去流量，反向边加上流量，这是 Ford-Fulkerson 算法的关键。

总结

通过本教程，你已经掌握了如何用 Java最大流算法 解决实际的 网络流问题。Ford-Fulkerson 方法虽然概念简单，但非常强大。配合 BFS（即 Edmonds-Karp），它能在 O(V·E²) 时间内求出最大流，适用于大多数中小型图。

建议你动手运行上面的代码，尝试修改图的结构，观察最大流的变化。这不仅能加深理解，还能帮助你在面试或项目中灵活应用 图论算法 解决复杂问题。

关键词回顾：Java最大流算法、Ford-Fulkerson算法、网络流问题、图论算法。