网络流入门：最大流、增广路与最小割

我对“网络流入门：最大流、增广路与最小割”的理解经历过一个从会背到会用的过程。其中最明显的一点是：网络流的反向边曾经最违反我的直觉：明明已经把流量送出去了，为什么还允许在残量网络里“退回来”。后来每次看到结论，我都会追问它省掉了哪一步、又付出了什么代价，这也是这篇文章的主线。

网络流是图论中比较进阶的一类问题。它关注的是：在每条边都有容量限制的网络里，从源点到汇点最多能输送多少流量。

它从哪里来

Ford 与 Fulkerson 在 1956 年提出通过增广路求最大流的经典框架。它的重要突破是残量网络：已经送出的流并非不可改变，反向边允许算法撤回早先选择，再寻找更好的整体分配。

网络流模型

图：每条边都有容量，最大流表示从 S 到 T 最多能送多少

网络流常见元素：

• 源点 S：流量出发点。
• 汇点 T：流量到达点。
• 容量 capacity：每条边最多能通过多少。
• 流量 flow：当前已经通过多少。
• 残量网络：还可以继续调整的空间。

最大流的直觉

最大流算法不是简单找一条路径，而是不断找“还能增广的路径”。每找到一条从 S 到 T 的可行路径，就沿路径增加流量。

如果之后发现之前走法不够好，可以通过反向边把部分流量退回来，再重新分配。

Edmonds-Karp 思路

Edmonds-Karp 是 Ford-Fulkerson 的 BFS 版本。每次在残量网络中找一条最短增广路。

伪代码：

while (存在从 S 到 T 的增广路) {
    delta = 路径上最小剩余容量;
    沿路径增加 delta;
    沿反向边增加 delta 的可回退容量;
}

这个算法好理解，但不是最快。学习入门时，它适合建立网络流直觉。

最大流最小割定理

最小割是把图切成两部分，使 S 和 T 分开，并让被切断边的容量和最小。

最大流最小割定理说明：

最大流的值 = 最小割的容量

直觉上，如果某些边形成瓶颈，所有流量都必须经过它们，那么无论怎么调度，最大流都不会超过这个瓶颈容量。

应用场景

网络流可以建模很多资源分配问题：

• 多源多汇物流分配。
• 带容量的任务调度。
• 图像分割中的最小割模型。
• 二分图最大匹配。
• 供应链、带宽、交通流量建模。

我的分析

网络流不建议作为数据结构与算法入门阶段的第一重点，但它应该在完整专题里出现。因为它代表了“图 + 约束 + 优化”的建模能力。

普通 BFS/DFS 解决可达性，最短路解决路径代价，最小生成树解决连接成本，而网络流解决容量约束下的整体输送能力。这个区别非常重要。

面试题

1. 最大流问题中的源点和汇点是什么？
2. 残量网络为什么需要反向边？
3. 增广路是什么意思？
4. 最大流和最短路有什么区别？
5. 二分图匹配为什么可以转成网络流？