Ford-Fulkerson算法

Ford-Fulkerson算法是一种经典的最大流算法，它的思想是通过不断地增广路径来找到最大流。它的时间复杂度为O(f * E)，其中f为最大流量，E为边的数量。

具体实现过程如下：

1. 初始化网络的流为0。

2. 不断寻找增广路径（即在残留网络中找到一条从源点到汇点的路径，路径上的边还没有达到最大流量）。

3. 对于找到的增广路径，计算其可增加的流量（即路径上最小的边的剩余容量），并更新网络流。

4. 重复步骤2和3，直到无法找到增广路径。

5. 返回最大流。

需要注意的是，Ford-Fulkerson算法中增广路径的选择可以采用不同的策略，如深度优先搜索、广度优先搜索、最短路搜索等，这些不同的策略会影响算法的效率和实现难度。

同时，由于Ford-Fulkerson算法是一种贪心算法，它可能会陷入死循环或者无法找到最优解。因此，后续的研究者提出了Edmonds-Karp算法和Dinic算法等改进算法，用于解决这些问题。

以下是Java代码实现

import java.util.LinkedList;

public class FordFulkerson {
    static final int V = 6; // 定义图中节点数
    static int[][] graph; // 定义邻接矩阵

    // 使用BFS寻找增广路径，返回是否存在增广路径
    static boolean bfs(int[][] residualGraph, int s, int t, int[] parent) {
        boolean[] visited = new boolean[V];
        LinkedList<Integer> queue = new LinkedList<>();
        queue.add(s);
        visited[s] = true;
        parent[s] = -1;

        while (!queue.isEmpty()) {
            int u = queue.poll();
            for (int v = 0; v < V; v++) {
                if (!visited[v] && residualGraph[u][v] > 0) {
                    visited[v] = true;
                    parent[v] = u;
                    queue.add(v);
                }
            }
        }
        return visited[t];
    }

    // Ford-Fulkerson算法求解最大流
    static int fordFulkerson(int[][] graph, int s, int t) {
        int u, v;
        int[][] residualGraph = new int[V][V]; // 定义残留网络
        for (u = 0; u < V; u++)
            for (v = 0; v < V; v++)
                residualGraph[u][v] = graph[u][v];

        int[] parent = new int[V]; // 记录BFS搜索树

        int maxFlow = 0; // 初始最大流为0
        while (bfs(residualGraph, s, t, parent)) {
            int pathFlow = Integer.MAX_VALUE;
            for (v = t; v != s; v = parent[v]) {
                u = parent[v];
                pathFlow = Math.min(pathFlow, residualGraph[u][v]);
            }
            for (v = t; v != s; v = parent[v]) {
                u = parent[v];
                residualGraph[u][v] -= pathFlow;
                residualGraph[v][u] += pathFlow;
            }
            maxFlow += pathFlow;
        }
        return maxFlow;
    }

    // 测试
    public static void main(String[] args) {
        graph = new int[][] { { 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 s = 0, t = 5;
        System.out.println("最大流量为：" + fordFulkerson(graph, s, t));
    }
}

其中bfs函数使用BFS算法寻找增广路径，并返回是否存在增广路径；Ford-Fulkerson函数则是使用Ford-Fulkerson算法求解最大流，具体实现过程已在前面介绍。