网络最大流计算器

网络最大流计算器

网络最大流计算器用于计算任何带容量的有向网络中从选定源点 s 到选定汇点 t 的最大流。在底层，它运行 Ford-Fulkerson 方法和广度优先增广路径（即 Edmonds-Karp 算法），并记录找到的每一条路径，以便您可以逐次迭代回放整个决策过程。结果页面还会显示最小割 —— 这是证明您的流值真正达到最优的瓶颈划分。

什么是最大流问题？

流网络是一个有向图 G = (V, E) 以及容量函数 c: E → ℝ_≥0。其中有两个特殊的顶点：源点 s（流的起点）和汇点 t（流的终点）。流 f 是分配给各条边且满足以下条件的赋值 f(u, v) ≥ 0：

最大流问题是寻找使 |f| 最大化的流 f。直观理解：如果边是具有给定容量的水管，您每秒可以从 s 运送到 t 多少升水？

算法原理 — 带 BFS 的 Ford-Fulkerson

该算法在维护当前流量的同时维护一个残余图。对于每一条容量为 c 且当前流量为 f 的边 (u, v)，残余图包含：

• 一条正向残余边 (u, v)，容量为 c − f（还可以推送多少流量），以及
• 一条反向残余边 (v, u)，容量为 f（可以取消多少已承诺的流量）。

在每次迭代中，它都会在残余图上执行从 s 到 t 的广度优先搜索 (BFS)。如果找到路径，则该路径上最小的边容量 —— 即瓶颈 —— 会被加到路径上每条正向边的流量中，并从每条反向边的流量中减去。这被称为增广路径。当 BFS 无法再到达 t 时，当前流量即为最优解。

使用 BFS（而非任意路径查找策略）将 Ford-Fulkerson 算法转变为 Edmonds-Karp 算法，其保证运行时间为 O(V · E²)。它还保证了在无理数容量情况下的终止，而普通 Ford-Fulkerson 则不能保证。

最大流最小割定理

割是将顶点划分为两个集合 (S, T) 的划分，其中 s ∈ S 且 t ∈ T。它的容量是从 S 到 T 的边的容量之和：

最大流最小割定理 (Ford & Fulkerson, 1956) 指出：

该工具会自动寻找最小割。在 Edmonds-Karp 算法终止后，它会在残余图上从 s 开始执行最后一次 BFS；到达的顶点形成 S，其余形成 T，原始图中所有从 S → T 跨越的边均已饱和。它们的容量总和恰好等于最大流值 —— 在结果顶部的“最小割容量 ✓ 验证了最优性”中可见。

专为学习设计的功能

• 逐步动画回放： 使用播放、暂停和单步控制回放每条增广路径。查看 BFS 选择了哪条路径、哪条边是瓶颈，以及总流量是如何增长的。
• 三个同步矩阵： 在容量矩阵 C、最终流量矩阵 f 和残余矩阵 C − f 之间切换 —— 这三幅图共同表征了任何流网络。
• 最小割划分视图： S 侧和 T 侧的顶点以芯片形式列出，跨越割的饱和边用红色突出显示。
• 逐边详情表： 显示每条边的容量、流量、残余量、利用率进度条和饱和标签。
• 分层布局： 图表绘制基于从源点开始的 BFS 距离计算，因此水流在视觉上从左向右“流动” —— 就像教科书里的画法一样。

输入格式

1. 带容量的边列表

每行一条边。箭头形式最易读，但也支持其他替代方案：

同时接受：A, B, 10 · A B 10 · A -> B , 10。同一对顶点之间的多条边将被累加。

2. 容量矩阵

每行输入一行数据，值之间用空格或逗号分隔。条目 C[i][j] 是从顶点 i 到顶点 j 的边的容量。无边请使用 0。矩阵必须是方阵，且对角线必须为 0（不允许自环）。

在矩阵标签字段输入对应的顶点标签（用逗号或空格分隔）。如果省略，标签默认为 S, A, B, …, T。

最大流的应用

操作实例

“教科书”快速示例编码了一个具有源点 S 和汇点 T 的 6 节点网络。运行 Edmonds-Karp 算法会产生四条增广路径：

1. S → A → B → T，瓶颈为 4（边 A-B 是限制因素）。当前总流量：4。
2. S → A → D → T，瓶颈为 6。当前总流量：10。
3. S → C → D → T，瓶颈为 4（边 D-T 现在是限制因素，仅剩 4 个单位）。当前总流量：14。
4. S → C → D → B → T，瓶颈为 5。当前总流量：19。

算法停止 —— 不再存在增广路径。最小割为 (S = {S, C}, T = {A, B, D, T})，跨越边为 S → A (容量 10) 和 C → D (容量 9)，总和为 19 —— 正好等于最大流值。

如何使用此计算器

1. 选择输入格式（使用选项卡） —— 边列表（推荐）或容量矩阵。
2. 输入您的网络。 您可以从快速示例开始并进行修改。对于矩阵输入，如果您想要 S, A, B, …, T 以外的名称，请提供标签。
3. 指定源点和汇点（或留空以自动检测 S 和 T）。
4. 点击计算最大流。 结果页面显示最大流值、最小割划分、分层图可视化、每条增广路径、边利用率表以及三个矩阵（容量、流量、残余）。
5. 播放图表下方的动画来回放算法的决策。点击任何增广路径步骤可直接跳至该步骤。

限制

• 顶点数： 最多 30 个 —— 以保持可视化和矩阵的可读性。
• 边数： 最多 200 条。
• 容量： 非负，最高达 10⁹。允许小数容量。
• 无自环： 在标准最大流公式中自环不携带任何流量，因此将被拒绝。

常见问题解答

什么是最大流问题？

给定一个有向网络，其中每条边都有一个非负容量，最大流问题是问：在满足每条边的流量不能超过其容量，且进入每个非源、非汇顶点的流量必须等于离开它的流量的规则下，从指定的源点 s 到指定的汇点 t 可以推送多少流量？答案被称为最大流值。

什么是 Ford-Fulkerson 方法？

Ford-Fulkerson 是计算最大流的一种通用技术。它在残余图中反复寻找从源点到汇点的增广路径，并沿该路径推送尽可能多的流量（瓶颈容量），然后更新残余图。当不存在增广路径时，程序终止。当使用广度优先搜索进行路径选择时，它被称为 Edmonds-Karp 算法，运行时间为 O(V · E²)。

流网络的最小割是什么？

割是将顶点划分为两个集合 S 和 T，使得源点在 S 中，汇点在 T 中。割的容量是从 S 到 T 的边的容量之和。最小割是容量最小的割。著名的最大流最小割定理证明了最大流值始终等于最小割容量，因此找到其中一个也就免费得到了另一个。

什么是残余图？

残余图跟踪每条边还可以推送多少流量。对于容量为 c 且当前流量为 f 的原始边 (u, v)，残余图包含一条正向边 (u, v) 与容量 c 减 f（剩余容量），以及一条反向边 (v, u) 与容量 f（可取消流量）。增广路径使用残余图中的边，使算法能够撤回之前的决定。

为什么该工具使用 BFS 寻找增广路径？

使用广度优先搜索 (Edmonds-Karp) 选择增广路径可以保证无论边容量如何，都能在多项式时间内终止。使用任意路径查找策略的普通 Ford-Fulkerson 在病态输入上可能会循环指数次迭代，在无理数容量上甚至可能永远不会终止。BFS 还会产生最短增广路径，更易于阅读和分析。

饱和边意味着什么？

当一条边的流量等于其容量时，该边即为饱和，这意味着无法再在其上推送更多流量。饱和边是网络的瓶颈，每个最小割完全由从割的 S 侧到 T 侧的饱和边组成。该工具用红色突出显示饱和边，让您一眼就能看到瓶颈结构。

延伸阅读

• 最大流问题 — 维基百科
• Ford–Fulkerson 算法 — 维基百科
• Edmonds–Karp 算法 — 维基百科
• 最大流最小割定理 — 维基百科