【数据结构与算法体系】之图算法（五）-最大流

一、网络流问题的数学定义

1.1 流网络（Flow Network）

流网络 $G = (V, E)$ 是一个有向图，满足：

容量（Capacity）：每条边 $(u, v) \in E$ 有非负容量 $c(u, v) \geq 0$。若 $(u, v) \notin E$ 则 $c(u, v) = 0$。
源点（Source）$s \in V$：唯一的”出发点”，只有出流，没有入流。
汇点（Sink）$t \in V$（$t \neq s$）：唯一的”目的地”，只有入流，没有出流。
每个顶点 $v \in V \setminus {s, t}$ 在至少一条 $s \rightsquigarrow t$ 的路径上（所有顶点都有用，可预先清理）。

1.2 流（Flow）的定义

流是一个函数 $f: V \times V \to \mathbb{R}$，满足两条约束：

(1) 容量约束：$\forall u, v \in V$，$0 \leq f(u, v) \leq c(u, v)$。

(2) 流量守恒（Flow Conservation）：$\forall u \in V \setminus {s, t}$，

$$\sum_{v \in V} f(v, u) = \sum_{v \in V} f(u, v)$$

即每个中间顶点的流入量等于流出量。

流的值：$|f| = \sum_{v \in V} f(s, v) - \sum_{v \in V} f(v, s)$。由于 $s$ 没有入边，通常 $|f| = \sum_{v \in V} f(s, v)$。

最大流问题：在所有可行流中，找到使 $|f|$ 最大的流 $f^*$。

1.3 流网络的可视化

          10          8
    a ─────────→ b ─────→ d
   ↗│          ↗│       ↗ │
s ──┼──→ 5     │4     3│  │
 5  │          │       │  │
   ↘│    15    │       │  │
    c ─────────┘       │  │
    │                  │  │
    └─── 6 ───→ t ←───┘  │
                  ← 10 ──┘

每条边上标注的是容量 $c$。目标：从 $s$ 向 $t$ 输送尽可能多的”物资”，不超出任何边的容量。

二、残量网络与增广路

2.1 残量网络（Residual Network）

给定流 $f$，残量网络 $G_f = (V, E_f)$ 刻画了”还可以如何调整流”：

前向边（Forward Edge）：对每条 $(u, v) \in E$ 且 $f(u, v) < c(u, v)$，在 $G_f$ 中添加边 $(u, v)$，残量容量 $c_f(u, v) = c(u, v) - f(u, v)$。表示还可以增加这么多流量。
后向边（Backward Edge）：对每条 $(u, v) \in E$ 且 $f(u, v) > 0$，在 $G_f$ 中添加边 $(v, u)$，残量容量 $c_f(v, u) = f(u, v)$。表示可以”撤销”这么多流量（通过反向推送）。

残量网络的直觉：后向边使得算法可以”反悔”——之前从 $u$ 推到 $v$ 的流，现在可以通过推送反向流到 $u$ 来修正错误的分配。

2.2 增广路（Augmenting Path）

增广路 $P$ 是 $G_f$ 中从 $s$ 到 $t$ 的一条简单路径。其瓶颈容量（bottleneck capacity）为：

$$c_f(P) = \min_{(u,v) \in P} c_f(u, v)$$

沿 $P$ 增广 $c_f(P)$ 单位流量：

对 $P$ 上的每条前向边 $(u, v)$：$f(u, v) \leftarrow f(u, v) + c_f(P)$
对 $P$ 上的每条后向边 $(v, u)$（原图中是 $(u, v)$）：$f(u, v) \leftarrow f(u, v) - c_f(P)$

关键性质：增广后流量仍满足容量约束和流量守恒。

三、Ford-Fulkerson 方法

3.1 通用框架

Ford-Fulkerson 是一个方法（Method），而非具体算法，因为它不指定如何寻找增广路。

FORD-FULKERSON-METHOD(G, s, t):
    for each edge (u,v) in E:
        f(u,v) = 0
    while 在残量网络G_f中存在从s到t的增广路P:
        c_f(P) = min{c_f(u,v) | (u,v)在P上}
        for each edge (u,v) in P:
            if (u,v)是G中的前向边:
                f(u,v) += c_f(P)
            else:
                f(v,u) -= c_f(P)   // 后向边：撤销流
    return f

3.2 最大流最小割定理（Max-Flow Min-Cut Theorem）

这是网络流理论的核心定理，也是所有最大流算法正确性的基础。

定义（割）：$s$-$t$ 割 $(S, T)$ 是将顶点集 $V$ 划分为两个子集，使得 $s \in S$，$t \in T$。割的容量定义为：

$$c(S, T) = \sum_{u \in S, v \in T} c(u, v)$$

定理：最大流的值等于最小割的容量。即：

$$\max_{f \text{ is a flow}} |f| = \min_{(S,T) \text{ is an s-t cut}} c(S, T)$$

证明概略（三步等价性）：

**(1) $|f| \leq c(S, T)$ 对任意流 $f$ 和割 $(S, T)$**：由流量守恒，净流量从 $S$ 流出到 $T$，受到每条横跨边的容量约束。
**(2) 若 $G_f$ 中不存在 $s \to t$ 的路径，则存在割 $(S, T)$ 使得 $|f| = c(S, T)$**：令 $S = {v \mid \text{在} G_f \text{中从} s \text{可达} v}$，则 $s \in S$ 且 $t \notin S$（否则存在增广路）。对该割，所有从 $S$ 到 $T$ 的原图边 $(u,v)$ 满足 $f(u,v) = c(u,v)$，所有从 $T$ 到 $S$ 的原图边 $(v,u)$ 满足 $f(v,u) = 0$。由此推出 $|f| = c(S, T)$。
(3) 当 Ford-Fulkerson 终止时，$f$ 是最大流：此时残量网络无增广路，由 (2) 构造的割容量 $=$ 当前流值，由 (1) 知这就是最大流。$\square$

四、Edmonds-Karp 算法

4.1 算法描述

Edmonds-Karp 算法是 Ford-Fulkerson 的第一个具体实现（用 BFS 寻找最短增广路——按边数最少）。

为什么 BFS？ 使用 DFS 可能在残量网络中反复绕路导致指数级迭代次数（经典反例：容量为无理数时可无限循环，容量为整数时可能需 $\Theta(|f^*|)$ 次增广）。BFS 确保每次增广路按边数最短，可以证明增广次数上界为 $O(VE)$。

4.2 完整 Java 实现

import java.util.*;

class EdmondsKarp {
    static final int INF = Integer.MAX_VALUE / 2;
    
    // 边类：to=目标, rev=反向边在adj[to]中的下标, cap=容量
    static class Edge {
        int to, rev, cap;
        Edge(int to, int rev, int cap) { this.to = to; this.rev = rev; this.cap = cap; }
    }
    
    public static long maxFlow(List<Edge>[] graph, int s, int t) {
        int n = graph.length;
        long flow = 0;
        int[] parent = new int[n];      // parent[v] = 到达v的边的"起点"
        int[] parentEdge = new int[n];  // parentEdge[v] = 边在adj[parent[v]]中的下标
        
        while (true) {
            // BFS 寻找最短增广路
            Arrays.fill(parent, -1);
            Queue<Integer> q = new LinkedList<>();
            q.offer(s);
            parent[s] = s;
            
            while (!q.isEmpty() && parent[t] == -1) {
                int v = q.poll();
                for (int i = 0; i < graph[v].size(); i++) {
                    Edge e = graph[v].get(i);
                    if (e.cap > 0 && parent[e.to] == -1) {
                        parent[e.to] = v;
                        parentEdge[e.to] = i;
                        q.offer(e.to);
                    }
                }
            }
            
            if (parent[t] == -1) break; // 无增广路
            
            // 回溯找到瓶颈容量
            int bottleneck = INF;
            for (int v = t; v != s; v = parent[v]) {
                int u = parent[v];
                Edge e = graph[u].get(parentEdge[v]);
                bottleneck = Math.min(bottleneck, e.cap);
            }
            
            // 增广
            for (int v = t; v != s; v = parent[v]) {
                int u = parent[v];
                Edge e = graph[u].get(parentEdge[v]);
                e.cap -= bottleneck;
                graph[v].get(e.rev).cap += bottleneck; // 反向边增加残量
            }
            
            flow += bottleneck;
        }
        return flow;
    }
    
    // 添加边的辅助方法（同时添加反向边）
    public static void addEdge(List<Edge>[] graph, int from, int to, int cap) {
        graph[from].add(new Edge(to, graph[to].size(), cap));
        graph[to].add(new Edge(from, graph[from].size() - 1, 0)); // 反向边初始容量0
    }
}

4.3 复杂度分析

定理：Edmonds-Karp 算法最多执行 $O(VE)$ 次增广。

证明概要：每次增广至少饱和一条边（该边在残量网络中的容量变为 0）。定义一条边 $(u, v)$ 的关键时间为其被饱和的时刻。可以证明：在每两次 $(u, v)$ 被饱和之间，从 $s$ 到 $u$ 的最短距离至少增加 2。由于 $s$ 到任意顶点的最短距离不超过 $V-1$，每条边最多被饱和 $O(V)$ 次。共有 $E$ 条边，因此总增广次数为 $O(VE)$。

每次 BFS 和增广耗时 $O(E)$，总时间 $O(VE \cdot E) = O(VE^2)$。

空间复杂度：$O(V + E)$（邻接表 + BFS 队列）。

五、Dinic 算法

5.1 核心概念：层次图（Level Graph）与阻塞流（Blocking Flow）

Dinic 算法引入了两个关键概念来减少 BFS 的次数：

层次图：从 $s$ 运行 BFS，记录每个顶点的层次（距离 $s$ 的边数）$level[v]$。层次图 $L$ 仅保留满足 $level[v] = level[u] + 1$ 的边。层次图是一个 DAG（有向无环图）。

阻塞流：在层次图中，一个流使得每条 $s \to t$ 路径上至少有一条边被饱和（即该边残量容量变为 0）。阻塞流不一定是最大流，但构造阻塞流后，残量网络中 $s$ 到 $t$ 的最短距离必然增加。

算法结构：

DINIC(G, s, t):
    flow = 0
    while 在G_f中能从s BFS到t:
        构建层次图L
        在L中寻找阻塞流f
        flow += f
    return flow

5.2 完整 Java 实现（带当前弧优化）

class Dinic {
    static class Edge {
        int to, rev, cap;
        Edge(int to, int rev, int cap) { this.to = to; this.rev = rev; this.cap = cap; }
    }
    
    static int[] level;  // level[v] = 层次
    static int[] iter;   // iter[v] = 当前弧（当前弧优化）
    
    public static long maxFlow(List<Edge>[] graph, int s, int t) {
        int n = graph.length;
        long flow = 0;
        level = new int[n];
        iter = new int[n];
        
        while (bfs(graph, s, t)) {
            Arrays.fill(iter, 0);
            long f;
            while ((f = dfs(graph, s, t, Long.MAX_VALUE)) > 0) {
                flow += f;
            }
        }
        return flow;
    }
    
    // BFS构建层次图
    private static boolean bfs(List<Edge>[] graph, int s, int t) {
        Arrays.fill(level, -1);
        Queue<Integer> q = new LinkedList<>();
        level[s] = 0;
        q.offer(s);
        
        while (!q.isEmpty()) {
            int v = q.poll();
            for (Edge e : graph[v]) {
                if (e.cap > 0 && level[e.to] < 0) {
                    level[e.to] = level[v] + 1;
                    q.offer(e.to);
                }
            }
        }
        return level[t] >= 0; // s能到达t
    }
    
    // DFS在层次图中寻找阻塞流
    private static long dfs(List<Edge>[] graph, int v, int t, long flow) {
        if (v == t) return flow;
        
        for (; iter[v] < graph[v].size(); iter[v]++) {
            Edge e = graph[v].get(iter[v]);
            if (e.cap > 0 && level[v] < level[e.to]) {
                long pushed = dfs(graph, e.to, t, Math.min(flow, e.cap));
                if (pushed > 0) {
                    e.cap -= pushed;
                    graph[e.to].get(e.rev).cap += pushed;
                    return pushed; // 找到一个阻塞流就返回
                }
            }
        }
        return 0;
    }
    
    // 添加边
    public static void addEdge(List<Edge>[] graph, int from, int to, int cap) {
        graph[from].add(new Edge(to, graph[to].size(), cap));
        graph[to].add(new Edge(from, graph[from].size() - 1, 0));
    }
}

5.3 复杂度分析

一般图：$O(V^2 E)$

BFS 构建层次图：$O(E)$，最多 $O(V)$ 次（每次层次图的最短距离严格增加）
一次 DFS 寻找阻塞流：$O(VE)$（每条边在每层最多饱和一次）
总计：$O(V^2 E)$

单位容量网络（每条边容量为 1）：$O(\min(V^{2/3}, E^{1/2}) \cdot E)$

单位容量网络且无平行边（如二分图匹配）：$O(\sqrt{V} \cdot E)$

为何 Dinic 在实践中极快：最坏情况复杂度虽然看着吓人，但在实际网络（特别是容量为整数的网络）中，Dinic 的表现远优于最坏情况分析。当前弧优化（iter 数组）避免重复扫描已饱和的边，贡献了大量常数优化。

六、Push-Relabel 算法（简介）

6.1 与增广路方法的本质区别

增广路方法（Ford-Fulkerson 范式）总是维护一个可行流，每次增加流量直到最大。而 Push-Relabel（推送-重标号）算法维护一个”预流（Preflow）”，允许中间顶点暂时拥有入超（excess），通过局部操作逐步将流量”推”向汇点。

核心操作：

Push（推送）：若顶点 $u$ 有入超（excess > 0）且存在残量边 $(u, v)$ 满足 $label[u] = label[v] + 1$，则将 $\min(excess[u], c_f(u, v))$ 单位的流从 $u$ 推到 $v$
Relabel（重标号）：若 $u$ 有入超但不存在可以推送的邻居（即对所有残量边 $(u, v)$ 有 $label[u] \leq label[v]$），则提升 $u$ 的标号：$label[u] \leftarrow 1 + \min{label[v] \mid c_f(u, v) > 0}$

复杂度：通用 Push-Relabel 为 $O(V^2 E)$，Relabel-to-Front 为 $O(V^3)$。

6.2 什么时候用 Push-Relabel？

在实际的大规模网络流问题中，Push-Relabel 和 Dinic 通常在性能上互有胜负。Push-Relabel 对于某些”高容量、复杂拓扑”的网络可能更快。但在大多数竞技编程和面试的场景中，Dinic 是更好的默认选择（实现简单、常数小、对二分图匹配特别优秀）。

七、最大流算法的全面对比

┌─────────────────┬──────────────┬──────────────┬──────────────┐
│     算法         │ Edmonds-Karp │    Dinic     │ Push-Relabel │
├─────────────────┼──────────────┼──────────────┼──────────────┤
│ 时间复杂度       │ O(V·E²)      │ O(V²·E)      │ O(V²·E)      │
│ 时间复杂度(单位) │ O(V·E²)      │ O(min(V²/³,  │ O(V·E)       │
│                 │              │  E¹/²)·E)    │              │
│ 增广路策略       │ BFS最短路    │ BFS层次+DFS  │ 局部推送      │
│ 实现难度         │ 简单         │ 中等          │ 复杂          │
│ 实际速度(一般)   │ 慢           │ 快            │ 较快          │
│ 二分图匹配       │ O(V·E²)      │ O(√V·E)      │ 不推荐        │
└─────────────────┴──────────────┴──────────────┴──────────────┘

选择建议：

面试/竞赛通用推荐：Dinic（代码不算太长，性能极好）
理解最大流原理：从 Edmonds-Karp 开始（BFS + 增广路概念清晰）
学习了就忘不了：实现一遍 Ford-Fulkerson with DFS（最简单，但注意容量类型）

八、经典应用

8.1 二分图最大匹配

问题：给定二分图 $G = (L \cup R, E)$，求最大匹配（边不共享顶点的最大子边集）。

流网络构造：

新增源点 $s$，从 $s$ 向所有 $L$ 中顶点连容量为 1 的边
新增汇点 $t$，从所有 $R$ 中顶点向 $t$ 连容量为 1 的边
原图中的边 $(u \in L, v \in R)$ 容量为 1（或 $\infty$，因为 1 已足够）

最大流的值就等于最大匹配的大小。最大流中的流分配直接给出了匹配方案。

int maxBipartiteMatching(int leftSize, int rightSize, List<int[]> edges) {
    int n = leftSize + rightSize + 2;
    int s = 0, t = n - 1;
    List<Dinic.Edge>[] graph = new List[n];
    for (int i = 0; i < n; i++) graph[i] = new ArrayList<>();
    
    // s → 左部
    for (int u = 1; u <= leftSize; u++) {
        Dinic.addEdge(graph, s, u, 1);
    }
    // 右部 → t
    for (int v = leftSize + 1; v <= leftSize + rightSize; v++) {
        Dinic.addEdge(graph, v, t, 1);
    }
    // 原边
    for (int[] e : edges) {
        int u = e[0] + 1; // 偏移 (s占用0)
        int v = e[1] + leftSize + 1;
        Dinic.addEdge(graph, u, v, 1);
    }
    
    return (int) Dinic.maxFlow(graph, s, t);
}

霍尔婚姻定理（Hall’s Marriage Theorem）提供了最大匹配大小的理论上界：最大匹配等于 $|L|$ 当且仅当 $\forall S \subseteq L, |N(S)| \geq |S|$。最大流实现隐式地验证了这一条件。

8.2 项目选择问题（Project Selection）

问题：有 $n$ 个项目，项目 $i$ 的收益为 $p_i$（可正可负）。某些项目之间存在前提依赖：做项目 $j$ 必须先做项目 $i$。选择项目子集最大化总收益。

转化为最小割：

正收益项目 $p_i > 0$：从 $s$ 连边，容量 $p_i$（切割该边 = 放弃正收益）
负收益项目 $p_i < 0$：向 $t$ 连边，容量 $-p_i$（切割该边 = 承担负收益）
依赖 $i \to j$：从 $i$ 向 $j$ 连无限容量边（确保若 $i$ 在 $S$ 中则 $j$ 也在 $S$ 中）

最大收益 = $\sum_{p_i > 0} p_i - \text{minCut}$，即”总正收益 - 最小割”。

8.3 图像分割（Graph Cut）

将图像像素建模为图中的顶点，相邻像素之间有条边。为每个像素给”前景”和”背景”概率评分，转化为源点和汇点的边容量。最小割给出最优的前景/背景分割。这就是 GrabCut 等经典图像分割算法的核心思想。

8.4 棒球淘汰问题（Baseball Elimination）

给定各队在剩余赛程中的对手，判断某支球队是否还有理论上的夺冠可能。可以转化为最大流检查：若某队赢下所有剩余比赛，其余球队的胜负能否不超过该队？建模为流网络，若最大流等于总剩余比赛场次，则该队仍有机会。

九、面试常见追问

问题一：为什么 Edmonds-Karp 使用 BFS 而不是 DFS？

回答：DFS 可能导致”绕远路”式的增广，在最坏情况下增广次数可以是指数级的。经典反例：一个简单的网络，若 DFS 运气不佳，每次只增广 1 单位流量，需要 $\Theta(|f^*|)$ 次增广（而最大流值本身可以达到 $2^{V/2}$）。BFS 保证沿着边数最少的路径增广，每条边被饱和 $O(V)$ 次，从而将增广次数限制在 $O(VE)$，保证了多项式时间。

Cormen 的经典案例：若用 DFS 交替走两条增广路，每次只有 1 单位流量被增广，对于容量为 $2 \cdot 10^9$ 的网络，需要运行 $2 \cdot 10^9$ 次增广。Edmonds-Karp 的 BFS 版本只做 2 次增广。

问题二：如何处理多个源点或多个汇点？

回答：添加超级源点和超级汇点。超级源点连接到所有原始源点，容量为 $\infty$；所有原始汇点连接到超级汇点，容量为 $\infty$。标准最大流算法即可处理。

问题三：如何处理顶点容量（Vertex Capacity）？

回答：将受容量限制的顶点 $v$ 拆分为两个顶点 $v_{in}$ 和 $v_{out}$，用一条容量等于顶点容量的边 $v_{in} \to v_{out}$ 连接。所有原本进入 $v$ 的边改为进入 $v_{in}$，所有离开 $v$ 的边改为从 $v_{out}$ 出发。

原图:  u → v → w   (顶点v容量 = C)
转换:  u → [v_in] --C--> [v_out] → w

问题四：最小割与最大流的关系——除了理论价值，最小割本身有什么实际意义？

回答：最小割在许多问题中直接就是答案：

网络可靠性：切断某些通信线路至少需要破坏多少带宽？
图像分割：前景和背景的分界线就是最小割
社区发现：社交网络中两个社区之间的”瓶颈”带宽
二元分类：对于马尔可夫随机场模型，最小割 = 最优分类

换句话说，最大流是”计算工具”，最小割才是很多问题的”真正答案”。

问题五：为什么 Dinic 算法在二分图匹配上特别快（$O(\sqrt{V}E)$）？

回答：在单位容量网络（特别是二分图匹配构造的流网络）中，Dinic 的一个关键性质是：在 $O(\sqrt{V})$ 次层次图构造后，阻塞流的大小变为 $O(\sqrt{V})$，剩下的增广次数也受到 $O(\sqrt{V})$ 的限制。因为每次层次图的最短距离增加至少 1，且最大增广路长度受限于 $2\sqrt{V}$（Hopcroft-Karp 分析的核心参数），所以总迭代次数为 $O(\sqrt{V})$，每次迭代 $O(E)$，总 $O(\sqrt{V}E)$。这就是 Hopcroft-Karp 二分图匹配算法的复杂度，而 Dinic 在单位容量网络上自动退化为此复杂度。

十、总结

网络流问题是算法设计中”归约（Reduction）”思想的极致体现——大量看似不相关的组合优化问题（二分图匹配、项目选择、图像分割、调度问题）都可以归约为最大流或最小割问题。

核心脉络：

残量网络 + 增广路：统一的理论框架
最大流最小割定理：所有最大流算法正确性的根基
Edmonds-Karp：BFS 保证多项式时间，$O(VE^2)$
Dinic：层次图 + 阻塞流 + 当前弧优化，实际性能最高，$O(V^2E)$

掌握了网络流，你就能用统一的语言描述并高效求解一大类组合优化问题。本系列将继续深入数据结构的基础：【数据结构与算法体系】表、栈和队列、【数据结构与算法体系】之摊还分析、【数据结构与算法体系】斐波那契堆等。网络流问题也是理解线性规划对偶性的绝佳入口——最大流最小割定理本质上就是线性规划强对偶定理在网络流问题上的特例。