最大流算法详解：Ford-Fulkerson 和 Edmonds-Karp 算法

求最大流的常用算法有 Ford-Fulkerson 算法和 Edmonds-Karp 算法。

1. Ford-Fulkerson 算法：

   • 初始化流量为 0。
   • 找到一条增广路径（即一条从源点到汇点的路径，且路径上的边还有剩余容量），计算该路径上的最小剩余容量。
   • 更新流量，将增广路径上的边的流量增加最小剩余容量。
   • 重复上述步骤，直到没有增广路径为止。此时，流量达到最大。

2. Edmonds-Karp 算法：

   • 初始化流量为 0。
   • 使用广度优先搜索 (BFS) 找到一条增广路径（即一条从源点到汇点的路径，且路径上的边还有剩余容量），计算该路径上的最小剩余容量。
   • 更新流量，将增广路径上的边的流量增加最小剩余容量。
   • 重复上述步骤，直到没有增广路径为止。此时，流量达到最大。

这两个算法的时间复杂度都是 O(E * |f|)，其中 E 为图的边数，|f| 为最大流量的大小。