最大流问题（Edmonds-Karp算法） 题目描述 最大流问题（Maximum Flow Problem）是图论中的一个经典问题，目标是在一个有向图中，从源点（Source）到汇点（Sink）的最大流量。图中每条边有一个容量（Capacity），表示该边能通过的最大流量。流量必须满足两个条件： 流量不超过边的容量。 除源点和汇点外，每个节点的流入流量等于流出流量（流量守恒）。 例如，一个管道网络，源点是水泵，汇点是用户，管道有最大流量限制，如何分配流量使得总流量最大？ 解题过程 Edmonds-Karp算法是Ford-Fulkerson方法的一种实现，通过BFS（广度优先搜索）寻找增广路径，确保每次找到的路径是最短的，从而保证算法效率（时间复杂度为O(V·E²)）。 步骤1：初始化残量图 残量图初始与原图相同，每条边的残量容量等于原始容量。 反向边的残量初始为0（用于流量调整）。 步骤2：循环寻找增广路径 使用BFS从源点s出发，寻找一条到汇点t的路径，路径上每条边的残量均需大于0。 如果找不到路径，算法结束，当前流量即为最大流。 步骤3：计算路径的最大流量 增广路径的最大流量由路径上最小残量决定（瓶颈边）。 例如路径s→a→b→t的残量分别为3、2、4，则最大流量为2。 步骤4：更新残量图 路径上所有正向边的残量减少流量值。 路径上所有反向边的残量增加流量值（允许后续反向调整流量）。 例如边(a,b)减少流量2，则反向边(b,a)增加流量2。 步骤5：累加总流量 将本次增广路径的流量值加到总流量中。 返回步骤2继续寻找下一条增广路径。 实例演示 假设图有4个节点：s（源点）、a、b、t（汇点），边容量为： s→a: 3, s→b: 2 a→b: 2, a→t: 2 b→t: 3 第1次BFS ：路径s→a→t，流量=min(3,2)=2。 更新：s→a残量=1，a→t残量=0，反向边a→s=2，t→a=2。 第2次BFS ：路径s→b→t，流量=min(2,3)=2。 更新：s→b残量=0，b→t残量=1，反向边b→s=2，t→b=2。 第3次BFS ：路径s→a→b→t，流量=min(1,2,1)=1。 更新：s→a残量=0，a→b残量=1，b→t残量=0，反向边相应调整。 结束 ：无法再找到增广路径，总流量=2+2+1=5。 通过BFS保证每次增广路径最短，避免Ford-Fulkerson可能因权重不合理导致的低效问题。