最大流最小割定理与Ford-Fulkerson算法详解

在很多人接触网络流的第一周几乎都会被“最大流”这个概念绕晕明明是一张带容量的有向图为什么能算出来的东西竟然能和一组边的“割”扯上关系而且关系还那么铁今天这篇就专门聊清楚两件事最大流怎么算以及为什么最大流的值永远等于最小割的容量。核心算法就是最经典的 Ford-Fulkerson 算法配合它衍生出的残量网络和增广路思想几乎是所有网络流入门的地基也是面试和校招里最常出现的图论考点之一。这篇内容适合刚接触网络流的人、正在刷算法题的读者以及要在实际项目里做带宽规划、任务调度或路径评估的工程师。我会从模型建立开始把每一步为什么这么做、反向边为什么存在、DFS 会踩哪些坑、怎么从计算结果里把最小割捞出来全部展开讲最后附上可跑的代码和工程选型建议。读完之后你可以直接把这个算法用在二分图匹配、项目排期、网络可靠性分析这些场景里。1. 最大流问题到底在解决什么1.1 从水厂管道说起先忘掉教科书上的符号定义。想象一个自来水厂通过一系列管道向用户供水。水厂是源点用户端是汇点中间有泵站、阀门、分支点这些就是节点管道有粗细和输送上限这个上限就是边的容量。问题很直接在每条管道都不超载的前提下单位时间里最多能送多少水到用户端这就是最大流问题。它不关心水具体走了哪条管道只关心总流量能不能达到全局最优。类似的场景还有交通路网里单位时间最多能通过多少辆车、数据中心里两个服务器之间最多能跑多少带宽、一个工厂的供应链最多能输送多少原材料到产线。把所有业务对象抽象成“节点 有向边 容量”最大流问题就出现了。注意我给的是有向图因为很多实际场景里流量是有方向性的。就算原问题是无向边比如一条双向公路我们也可以把它拆成两条反向有向边每条容量都是原容量这样处理起来更统一。1.2 可行流与流量守恒一个合法的流不是随便给每条边分配一个不大于容量的数就行了。它必须满足两个硬性条件第一个是容量限制任何一条边上的流量不能超过容量上限。第二个是流量守恒除了源点和汇点之外每个节点的流入量必须等于流出量。你可以把中间节点理解成一个中转仓库进来的货不能凭空消失也不能凭空变多进多少就得出多少。在这两个条件下从源点往汇点方向流动的总量就叫流的值。最大流问题就是在所有满足约束的合法流里找值最大的那个。有些初学者容易误解觉得流量守恒就意味着整体流量是固定的其实不是。源点可以无限往外“泵水”汇点可以无限“吸水”只有中间节点被约束住。所以不同的分配方案会让最终总流量差别很大这就是我们做优化算法的原因。1.3 这个模型为什么无处不在我以前接触过一个实际项目要评估一个通信网络里两个核心节点之间能承载多少并发流量。把设备抽象成节点、链路抽象成边、带宽抽象成容量之后整个评估就纯粹变成了最大流计算非常干净。更妙的是最大流的对偶问题也就是最小割在很多场景里反而是更重要的输出。什么叫最小割简单说就是把图切一刀把节点分成包含源点的集合 S 和包含汇点的集合 T割的容量是所有从 S 指向 T 的边容量之和。最小割就是所有切法里容量最小的那一个。它回答的是另一个非常实际的问题如果要让源点和汇点彻底断连最少需要切断多少容量放到网络安全里这就是找关键链路放到项目排期里这就是找资源瓶颈放到图像分割里这就是把前景和背景分开的最优边界。所以你会发现最小割这个词在最近的讨论热度很高因为很多实际问题更关心“哪里是瓶颈”而不是“最大能流多少”。好消息是这两个问题可以直接通过同一个算法一次解决。2. Ford-Fulkerson算法的核心原理2.1 残量网络算法的基础设施Ford-Fulkerson 算法的思想非常朴素一句话概括只要还能从源点找到一条通往汇点的路径就沿着这条路输送流量直到塞不下为止。但这里有个关键问题怎么定义“还能走”如果图中本来就只有从源到汇的有向路径那问题太简单了。麻烦的是我们一开始选的路径可能不够好后面想反悔怎么办真实世界里不太好反悔但算法里可以。Ford-Fulkerson 的设计引入了一个非常重要的概念残量网络。它有两个组成部分一是每条边上还没有用完的剩余容量也就是我们可以继续往上加流的空间二是为每条边建立一条反向边反向边的“容量”等于当前已经流过的流量表示我们有机会把之前分配的流量撤销回来。很多人第一次学这个算法时都被反向边搞得一头雾水。我当初也是。后来我想通了一个类比正向边是“你还能用多少容量”反向边是“你后悔了可以把容量要回来”。每一轮找路径时我们实际上是在残量网络里找一条从源到汇的路径不区分这条路径是由原始的正向边还是反向边组成的。走正向边表示新增流量走反向边表示撤销部分已有流量。允许走反向边就是允许算法修正自己之前的选择这一点至关重要。2.2 增广路径与主循环在残量网络里找到一条从源点 s 到汇点 t 的路径这条路径叫做增广路径。沿着这条路径能增加的流量上限取决于路径上所有残量的最小值也就是瓶颈值。我们可以把这条路径上每条边的残量都减去瓶颈值同时把对应的反向边残量加上瓶颈值一轮增广就完成了。算法的主循环非常简单初始化所有边的流量为 0。在残量网络中寻找一条从 s 到 t 的增广路径。如果找不到算法结束当前流就是最大流。如果找到了计算路径上的瓶颈值更新路径上所有边的残量回到第 2 步。循环的终止条件值得琢磨一下为什么没有增广路径当前流就是最大流这不是一个“看起来挺对”的直觉它背后有一个严格的理论支撑就是最大流最小割定理。我们稍后会详细推一遍。现在你只要先接受一个事实残量网络中是否还存在 s 到 t 的路径与当前流是否最优是等价的判断条件。2.3 反向边到底解决了什么我举一个特别容易理解的例子。假设图里有这样一条路径s 可以直接连到 a容量为 10s 也可以直接连到 b容量为 5a 连到 b容量为 3a 连到 t容量为 4b 连到 t容量为 8。如果第一轮增广选择了 s - a - b - t 这条路径瓶颈值是 3因为 a 到 b 只有 3我们会把 3 的流量灌进去。之后残量网络中s 到 a 的残量变成 7a 到 b 的残量变成 0b 到 t 的残量变成 5同时出现了三条反向边 t - b、b - a、a - s容量分别为 3、3、3。这时候如果只看原始图s 到 a 还剩 7a 到 t 还剩 4s 到 b 还剩 5b 到 t 还剩 5好像已经没法再增广了。但残量网络里存在一条路径s - b - a - t。你注意这里走了 b - a 这条反向边表示我们撤销了之前从 a 流向 b 的 3 个单位流量。这条路径的瓶颈值是 min(5, 3, 4) 3所以还能再增广 3。最终总流量是 6比第一次贪心的 3 高了一倍。如果没有反向边这个算法很容易掉进局部最优里出不来。所以说反向边不是算法的“附加功能”而是整个算法的灵魂。它把“流量的再分配”转化为“在残量网络上找路径”的数学操作非常优雅。3. 完整实现过程与代码细节3.1 邻接矩阵还是邻接表先决定数据结构。Ford-Fulkerson 的实现一般用邻接矩阵或者邻接表。对于算法验证和小规模图邻接矩阵非常直观capacity[u][v] 就表示 u 到 v 的容量代码可读性高写起来也快。缺点是空间复杂度是 O(V²)当节点数到几千甚至上万时就比较吃力而且矩阵还不好处理“同一条边反复插入”的情况。实际刷题和工程项目里我更推荐邻接表 边索引的方式。每条边存 to、capacity同时再存一条反向边的索引。更新的时候正向边容量减反向边容量加可以直接通过边索引找到另一半不用去遍历找对应边。这种方式空间是 O(E)而且天然支持存多条边适合稀疏图和大图。3.2 一个可运行的 Python 实现下面给一个用邻接表实现的完整版本。这个版本用 BFS 找增广路径严格来说已经属于 Edmonds-Karp 算法但它依然是 Ford-Fulkerson 思想的一个具体落地而且用 BFS 能保证增广路径最短避免 DFS 在某些数据下出现接近指数级递归的问题。from collections import deque class Edge: def __init__(self, to, rev, cap): self.to to # 边的终点 self.rev rev # 反向边在邻接表中的下标 self.cap cap # 当前剩余容量 def add_edge(graph, fr, to, cap): forward Edge(to, len(graph[to]), cap) backward Edge(fr, len(graph[fr]), 0) graph[fr].append(forward) graph[to].append(backward) def bfs(graph, s, t, parent_edge): visited [False] * len(graph) visited[s] True q deque([s]) while q: v q.popleft() for i, e in enumerate(graph[v]): if not visited[e.to] and e.cap 0: visited[e.to] True parent_edge[e.to] (v, i) if e.to t: return True q.append(e.to) return False def ford_fulkerson(graph, s, t): max_flow 0 INF 10 ** 18 parent_edge [None] * len(graph) while bfs(graph, s, t, parent_edge): # 找出路径上的瓶颈值 v t flow INF while v ! s: u, idx parent_edge[v] flow min(flow, graph[u][idx].cap) v u # 更新正向和反向边容量 v t while v ! s: u, idx parent_edge[v] reverse_edge graph[u][idx] reverse_edge.cap - flow graph[v][reverse_edge.rev].cap flow v u max_flow flow return max_flow使用方式非常简单先建图然后调用 ford_fulkerson。这个代码里的 add_edge 一次就创建好正向边和反向边反向边初始容量为 0。更新时正向边的 cap 减少反向边的 cap 增加语义上就等同于撤销流量。另外注意这里找增广路径用 BFS 而不是 DFS原因后面会展开说。如果你不需要最短增广路只是验证 Ford-Fulkerson 概念本身可以把 BFS 换成 DFS代码逻辑基本不变。3.3 DFS 找增广路径的隐患很多教材直接用 DFS 实现 Ford-Fulkerson。写法上很简洁递归函数的逻辑就是从当前节点出发找一条能到汇点且残量大于 0 的边递归下去回溯时返回路径上的最小残量。但在工程数据下DFS 版本存在一个让人头疼的问题每次找到的路可能很长很曲折更新完以后下一次 DFS 又可能把同样的路径重新走一遍反复消耗导致增广次数非常多。最坏情况的时间复杂度是 O(max_flow * E)什么意思呢如果最大流的值是 10 万图里有 1 万条边那可能要执行 10 亿次边遍历直接超时。这个问题有专门的构造例子被称为“Ford-Fulkerson with DFS 的病理学反例”。所以我在实际工程里几乎不用纯 DFS至少会加一个小优化每次都从源点开始用 DFS 深度受限地寻找一条可增广路径并且记录访问过的节点避免环路。但即便如此仍然没解决最坏情况问题。3.4 复杂度到底怎么算Ford-Fulkerson 每次增广至少增加 1 个单位的流量所以增广次数不超过最大流的值每次找增广路径的开销在最坏情况下是 O(E) 或 O(VE)取决于你用的是 BFS 还是 DFS。因此总复杂度是 O(max_flow * E)。如果容量都是整数这个上限是有意义的因为最大流值有限。但如果容量是实数或者容量特别大的浮点数算法可能陷入不终止的循环这是一个理论上必须注意的问题。把找增广路径的 DFS 换成 BFS 之后Edmonds-Karp 算法可以保证最多执行 O(V * E) 次 BFS整体复杂度就是 O(V * E²)。这个上界对整数和实数容量都成立。更高效的做法是 Dinic 算法它引入了分层图和多路增广复杂度是 O(V² * E)在竞赛和工业界里是使用最广泛的网络流算法。我个人的建议是如果你想彻底理解网络流的本质先用 DFS 版本的 Ford-Fulkerson 跑通小样例体会反向边和增广路径真正面对实际数据时直接上 Edmonds-Karp 或 Dinic效率差距不是一点半点。4. 最大流与最小割一枚硬币的两面4.1 什么是最小割把图的顶点集 V 分成两个非空集合 S 和 T要求源点 s 必须属于 S汇点 t 必须属于 T。所有从 S 指向 T 的有向边的容量之和叫做这个割的容量。最小割就是所有可能的割法中容量最小的那一个。这里的“割”不是把边的物理结构切断而是从逻辑上划分两个阵营。容量越小的割代表破坏源、汇连通性需要付出的代价越小。如果实际背景是网络攻击最小割就是最脆弱的链路集合如果实际背景是供应链最小割就是最约束产能的卡脖子环节。有一个非常容易混淆的点割的容量只计算从 S 到 T 的边不计算从 T 到 S 的边。为什么因为我们要考察的是“从源点阵营流向汇点阵营的通道”反向的边不会帮助源点向汇点输送流量所以就算它的容量再大也不应该计入割的代价。4.2 最大流等于最小割这个结论叫最大流最小割定理。它可以被拆成两步来理解。第一步任意一个流的值都不超过任意一个割的容量。道理很简单任何从源到汇的流量最终都必须穿过 S 和 T 的分界线。因为 S 里的流量守恒流出 S 的总量等于流入 S 的总量加上源点注入的总量而源点注入的总量就是流的值。所有从 S 流到 T 的流量加在一起必须经过那些从 S 指向 T 的边所以流的值不可能超过这些边的容量之和。这是一个朴素的“水桶效应”。第二步如果残量网络中不存在从 s 到 t 的路径那当前流就是一个割的容量恰好等于流值的割。做法很简单把残量网络中所有从 s 可达的节点放进集合 S剩下的放进 T。因为不存在从 s 到 t 的路径所以 t 不可能在可达集合里这确实是一个合法的割。把所有从 S 指向 T 的边找出来每一条边的正向残量一定为 0否则 t 就能通过这条边扩展到 T矛盾。既然残量为 0说明这些边的容量已经全部被当前流占用所以它们从 S 流向 T 的流量之和恰好等于这些边的容量之和也就是割的容量。另一方面从 T 指向 S 的边不会给总流量做贡献所以我们构造出的这个割其容量就等于当前流的值。结合第一步当前流的值等于割的容量而任意流都不超过任意割所以当前流就是最大流这个割就是最小割。整个证明干净利落这也是我认为网络流里最优雅的定理之一。4.3 如何从算法结果中提取最小割这个提取过程特别实用。算法终止时我们已经在残量网络中跑过一轮 BFS 或 DFS记录从 s 可达的顶点集合。把这些可达顶点全部标记为 S剩下的为 TS 到 T 的所有正向原始边就是最小割。用上一节 Python 代码实现的话只需要在最后一次 BFS 失败之后看一下 visited 数组里哪些节点是 True就得到了 S。然后遍历原图的所有正向边如果起点在 S 且终点不在 S这条边就是最小割中的一条边。要注意的是在邻接表实现里你存的正向边和反向边是成对出现的区分方式一般是检查这条边是不是 add_edge 时创建的正向边。在代码上可以给 Edge 加一个 is_forward 标记或者在生成边时记录下原始正向边的索引。我尝试过在一个 50 个节点、200 条边的随机图上跑了一遍最后提取出来的割边集合容量总和确实等于最大流值。这种“算法结果直接告诉我们瓶颈在哪里”的能力在实际项目里极有价值。4.4 最小割在图像分割里的经典应用最小割不只是理论概念它在很多实际问题里都有直接落地。最有名的要数图像分割。把每个像素看作图里的一个节点相邻像素之间连一条边边的容量表示两个像素的相似程度相似度越低容量越小表示越可能被切分开。另外再设置两个特殊的种子点前景种子连接源点背景种子连接汇点。求这个图的最小割效果就是把图像所有像素分成前景和背景两个集合使得分割代价最小也就是分割边界尽量沿着像素差异大的位置走。这个做法本质上是把“怎么切图最合理”变成了一个标准的图优化问题而求解工具正是网络流的最小割。所以你会看到最小割算法的热度在计算机视觉和图形学领域一直居高不下它已经远远超出水管和交通路网的范畴。5. 工程实践常见问题与算法选型5.1 新手最容易踩的几个坑第一个坑写 DFS 时忘了记录访问节点。网络流图里可能存在环忘了标记 visited 会让递归永远跑不完严重时导致栈溢出。这不是理论问题是我见过最多的运行时错误。第二个坑容量数据类型的精度问题。如果容量用整数挺安全。但如果用 double 求最小割比如图像分割中的权重值浮点误差可能让等值边被反复增广特别是在终止判断时残量小于 1e-9 的边到底算 0 还是不算 0不同实现会有不同结果。我的经验是先用整数处理能处理的问题实在要浮点数就设置一个精度阈值比如小于 1e-8 就视为 0。第三个坑邻接表更新反向边时写错了索引。每次更新边都要同时找到正向边和反向边。如果建图时没有记录好 rev 索引代码里就容易更新错边。解决方法是强制所有新增边都通过 add_edge 函数创建不要手写 Edge 对象。第四个坑最小割求的不是“所有割边”的集合是不是唯一。对于同一个最小割值可能存在多组不同的割边集合。算法终止时从 s 可达的集合对应的割是其中之一但不一定是业务上最想要的。如果需要找出所有最小割需要做额外处理。5.2 主流算法怎么选下面这张表是我的经验总结可以直接拿来参考算法时间复杂度适用场景优势劣势Ford-FulkersonDFSO(max_flow * E)教学、小图验证实现简单易于理解大数据下可能非常慢Edmonds-KarpBFSO(V * E²)中等规模图上界可控不容易被卡稠密图仍然偏慢DinicO(V² * E)绝大多数竞赛和工程场景分层图搭配多路增广实际效率很高实现略复杂Push-Relabel预流推进O(V² * E)超大图全局流场理论性能强适合并行实现复杂调试难度大如果只是做课程作业或者验证小图直接上 DFS 版就行重点是理解思想。如果你在刷题或者做中等规模的工程计算我建议至少用 Edmonds-Karp代码量只比 DFS 多十几行但稳定性提高一个量级。如果节点数超过 1000或者边数超过 10000最好直接上 Dinic它的分层图优化在绝大多数稀疏图上效果都好到离谱。5.3 怎么用最大流解决二分图匹配说一个最容易上手的应用二分图最大匹配。把左边集合的每个节点都与源点连一条容量为 1 的边把右边集合的每个节点都与汇点连一条容量为 1 的边中间的可匹配关系连容量为 1 的边。对这个图跑最大流得到的最大流值就是最大匹配数匹配边就是那些流过流量为 1 的中间边。这个方法的好处是你能用同一个网络流模板解决很多看似不相关的问题不用重新发明算法。比如任务分配左边是人右边是任务容量都为 1每条可执行的关系连容量为 1最大化成功分配的任务数量。再比如课程安排老师、教室、时间段的组合关系都可以通过建图转化为最大流问题。另一个有意思的扩展是带权二分图匹配它需要跑最小费用最大流。这个算法本质上是把 Ford-Fulkerson 的“容量”维度和一个“费用”维度结合在一起每次增广时优先找费用最小的路径。套路是完全一样的只是把找增广路径变成了最短路问题。5.4 结合“最小割”热词的落地思路最近看到很多讨论都在提最小割但不少初学者只是把最小割当作最大流的附属品。我想强调一点在很多实际业务里你真正要的不是最大流而是最小割。举个例子你想评估某个数据传输网络中两个服务之间的链路如果被若干条线路同时故障最少会断掉多少带宽。这本质上就是求最小割。你不需要真的把流量跑满你只需要算出最小的割容量就能知道最坏情况下的通信降级程度。再比如商品推荐场景里你要把用户分成“高活跃”和“低活跃”两个群体可以构图用户是节点用户之间的相似度是边容量然后不断调整源点和汇点的连接方式跑最小割来做聚类。这种目标函数和网络流结合的方法在一些业务分析里能替代简单的阈值划分给出的分组边界更有全局性。我的建议是下次遇到一个“需要把图分成两块并让切割代价最小”的需求先别急着上启发式算法试一下网络流最小割很可能结论又干净又稳定。最后再分享一点个人经验我第一次完整跑通 Ford-Fulkerson 时其实是在调一个二分图匹配的模板题。当时死活用 DFS 版本超时后来换成 BFS 版本才过于是我把反向边改来改去调了半天才发现问题不在反向边而在于我没有正确标记访问节点导致多轮增广始终在绕圈子。从那一刻起我养成了一个习惯但凡写网络流第一步先把建图函数 add_edge 写对第二步再写主循环每次增广后都 print 一下当前最大流值小数据手工验算一遍再上大数据。这个习惯帮我省了太多时间。网络流的代码看似简单但一旦出 bug排查成本远高于普通图算法因为错误可能藏在你完全想不到的反向边更新里。建议你也按照这个思路来先用 5 个节点的极简图跑通流程再逐步增加节点数和边数每一步都验证结果。只要把基础底盘打稳了后面学 Dinic 和费用流都会顺很多。