如何从给定有向图中提取最大流对应的实际流图？

你对Ford-Fulkerson类算法的认知存在偏差，这类算法本身就支持输出最大流对应的实际流图，不需要额外查找其他算法。

核心原理 #

Ford-Fulkerson及其衍生实现（Edmonds-Karp、Dinic等）运行过程中都会维护残量网络：对原始图中每条容量为c的正向边u→v，残量网络会同步构建一条容量为0的反向边v→u。算法每找到一条增广路并推送大小为f的流量时，会将正向边的剩余容量减f，同时将反向边的容量加f。
因此算法终止得到最大流后，反向边v→u的容量就是原始边u→v上承载的实际流量。

实现步骤 #

• 运行你选定的最大流算法至终止，得到最大流数值
• 遍历原始图的所有原始边u→v，读取残量网络中对应反向边v→u的容量，即为该边的实际流量f(u,v)
• 可选过滤掉f(u,v)=0的边，将剩余边和对应流量组合，就是你需要的最大流实际流图

实现注意事项 #

• 若用邻接矩阵存储残量网络，直接读取residual[v][u]即可得到u→v的实际流量
• 若用邻接表存储残量网络，通常每条正向边会存储对应反向边的索引，直接读取反向边的capacity属性即可

内容的提问来源于stack exchange，提问作者Ramish Siddique