网络流基础：从零开始理解“流”这件事
说实话，网络流这个概念，我第一次接触的时候也觉得挺抽象的。什么叫“流”？水管里的水？还是马路上的车？其实你想想看，计算机科学里的网络流，本质上就是在说一件事：在一个有容量限制的图中，怎么从源点往汇点尽可能多地输送“东西”。
我个人习惯把网络流想象成一个城市供水系统。源点是水库，汇点是居民区，中间那些管道就是边，每条管道有它的最大输水能力——这就是容量。而实际流过去的水量，就是流量。
基本概念：容量、流量、可行流
先来几个硬核定义，别怕，我尽量说人话。
- 容量（Capacity）：每条边能承受的最大流量。记作 c(u, v)。
- 流量（Flow）：实际流过边的量。记作 f(u, v)。
- 可行流（Feasible Flow）：满足两个条件的流——容量限制（f ≤ c）和流量守恒（除了源点和汇点，每个节点流入等于流出）。
- 最大流（Maximum Flow）：从源点到汇点能输送的最大可行流量。
核心要点：最大流问题就是找一组可行流，让源点流出的总量最大。
我在项目中遇到过这样一个场景：做视频直播的带宽调度，服务器集群之间有很多链路，每条链路带宽有限。我们需要计算从编码服务器到CDN节点的最大吞吐量。这不就是典型的网络流问题吗？
Ford-Fulkerson 方法：增广路的思想
Ford-Fulkerson 不是具体的算法，而是一种方法框架。它的核心思想很简单：
- 从零流量开始。
- 找一条从源点到汇点的路径，路径上每条边还有剩余容量（这叫增广路）。
- 沿着这条路尽可能多地增加流量。
- 重复，直到找不到增广路为止。
这里有个关键点——反向边。为什么要反向边？
嗯，这个问题我当年也困惑过。说白了，反向边是为了“反悔”。你想想看，第一次选的路径可能不是最优的，反向边允许你把已经分配的流量“退回去”，重新调整。没有反向边，算法就变成了贪心，很容易陷入局部最优。
小技巧：实现时，每条正向边对应一条容量为0的反向边。每次增加流量时，正向边减，反向边加。这样就能实现流量的“撤销”操作。
Edmonds-Karp 算法：BFS 找增广路
Ford-Fulkerson 方法有个问题——如果每次找增广路都乱找，可能会很慢，甚至死循环。Edmonds-Karp 算法就是给这个方法加了一个约束：每次用 BFS 找最短的增广路（边数最少）。
这样做的好处是时间复杂度有保证：O(V × E²)。虽然不算快，但胜在稳定、好理解。
// Edmonds-Karp 算法核心代码（C语言风格伪代码）
int bfs(int s, int t) {
memset(pre, -1, sizeof(pre));
queue<int> q;
q.push(s);
pre[s] = s;
while (!q.empty()) {
int u = q.front(); q.pop();
for (每个邻接点 v) {
if (pre[v] == -1 && capacity[u][v] > 0) {
pre[v] = u;
if (v == t) return 1;
q.push(v);
}
}
}
return 0;
}
int edmondsKarp(int s, int t) {
int maxFlow = 0;
while (bfs(s, t)) {
int flow = INF;
for (int v = t; v != s; v = pre[v]) {
int u = pre[v];
flow = min(flow, capacity[u][v]);
}
for (int v = t; v != s; v = pre[v]) {
int u = pre[v];
capacity[u][v] -= flow;
capacity[v][u] += flow;
}
maxFlow += flow;
}
return maxFlow;
}
我曾经用这个算法做过一个网络带宽分配的小工具。数据量不大，几百个节点，跑起来很稳。但如果你遇到上万节点的图，Edmonds-Karp 就有点吃力了。
Dinic 算法：分层图 + 多路增广
Dinic 算法是我个人最常用的最大流算法。它比 Edmonds-Karp 快得多，时间复杂度 O(V² × E)，实际表现往往更好。
Dinic 的核心思路分两步：
- BFS 建分层图：给每个节点标一个层级（距离源点的最短边数）。
- DFS 多路增广：在分层图上，一次 DFS 可以找到多条增广路，而不是一条一条找。
为什么要分层？说白了，就是防止 DFS 走回头路。有了层级约束，DFS 只能从低层走向高层，不会绕圈子。
// Dinic 算法核心代码（C语言风格）
int bfs() {
memset(level, -1, sizeof(level));
queue<int> q;
q.push(s);
level[s] = 0;
while (!q.empty()) {
int u = q.front(); q.pop();
for (每条边 e 从 u 出发) {
if (level[e.to] == -1 && e.cap > 0) {
level[e.to] = level[u] + 1;
q.push(e.to);
}
}
}
return level[t] != -1;
}
int dfs(int u, int flow) {
if (u == t) return flow;
for (int &i = cur[u]; i < G[u].size(); i++) {
Edge &e = edges[G[u][i]];
if (level[e.to] == level[u] + 1 && e.cap > 0) {
int pushed = dfs(e.to, min(flow, e.cap));
if (pushed > 0) {
e.cap -= pushed;
edges[G[u][i] ^ 1].cap += pushed;
return pushed;
}
}
}
return 0;
}
int dinic() {
int maxFlow = 0;
while (bfs()) {
memset(cur, 0, sizeof(cur));
while (int pushed = dfs(s, INF)) {
maxFlow += pushed;
}
}
return maxFlow;
}
注意：Dinic 中有一个优化叫“当前弧优化”（cur 数组）。它的作用是避免每次 DFS 都从第一条边开始遍历。我刚开始写的时候忘了加这个优化，结果在大图上跑得巨慢。加上之后，速度提升非常明显。
三种方法对比
| 算法 | 时间复杂度 | 适用场景 | 个人评价 |
|---|---|---|---|
| Ford-Fulkerson | O(E × |f|) | 小规模、教学演示 | 理解思想用，实际很少直接用 |
| Edmonds-Karp | O(V × E²) | 中小规模、边数不多 | 稳定，适合入门 |
| Dinic | O(V² × E) | 大规模、竞赛常用 | 我的首选，又快又稳 |
知识体系图
下面这张图帮你理清本章的知识脉络：
避坑指南
我曾经在一个项目里用 Dinic 处理一个 5000 节点、10 万条边的图。第一次跑的时候，内存直接爆了。后来发现是邻接表实现时，每条边都存了正向和反向两份，但忘记用“成对存储”的技巧（索引 i 和 i^1 互为反向边）。
还有一次，我写 Edmonds-Karp 时，BFS 里忘记判断容量大于 0，结果死循环了。嗯，这种低级错误，谁还没犯过呢？
我的建议：初学者先从 Edmonds-Karp 入手，理解增广路和反向边的思想。等熟练了再上 Dinic。别一上来就搞最复杂的，容易劝退。
好了，网络流的基础概念和三大算法就讲到这里。记住一句话：最大流问题的本质，就是在有容量限制的图中，找到从源到汇的最大输送量。后面的章节我们会继续深入，看看最大流在实际问题中怎么用。