数据结构与算法 / 系统课时
流网络建模
流网络建模
本课把运输、带宽或任务分配问题抽象成流网络。你将学会识别源点、汇点、容量与流量,并判断一个候选方案是否同时满足容量约束和流量守恒。
学习目标
- 识别流网络中的源点、汇点、容量、流量和流值。
- 使用容量约束与流量守恒判断可行流。
- 将真实问题转换为有向图中的顶点、边和容量。
模型要素与约束
流网络是一个带容量的有向图,通常记为 G = (V, E)。源点 s 只负责向网络输入流量,汇点 t 负责接收流量,边 (u, v) 的容量 c(u, v) 表示该方向最多允许通过多少流量。

一个流 f 要成为可行流,必须满足以下规则:
- 容量约束:每条边都有
0 ≤ f(u, v) ≤ c(u, v)。 - 流量守恒:除
s与t外,每个顶点的流入量等于流出量。 - 流值一致:源点净流出量等于汇点净流入量。
例如,边标记 3/5 表示当前流量为 3,容量为 5,剩余可用容量为 2。容量描述上限,流量描述当前方案,两者不能混为同一个数。
可行流判断
判断一个候选流时,可以为每个顶点维护余额:流入记为正,流出记为负。普通顶点余额必须为 0;源点余额为负,汇点余额为正,且两者绝对值相等。
这一判断只验证“当前流是否合法”,并不保证流值已经最大。最大流算法还需要利用剩余网络寻找增广路径,从而继续增加源点到汇点的净流量。
完整可运行示例
下面的 Java 17 程序建立一个四顶点流网络,并验证给定流量是否构成可行流。将代码保存为 FlowNetworkDemo.java。
import java.util.List;
public class FlowNetworkDemo {
private record Edge(int from, int to, int capacity, int flow) {
}
public static void main(String[] args) {
int source = 0;
int sink = 3;
int vertexCount = 4;
// 顶点 0 为源点,顶点 3 为汇点。
List<Edge> edges = List.of(
new Edge(0, 1, 5, 3),
new Edge(0, 2, 4, 2),
new Edge(1, 2, 2, 1),
new Edge(1, 3, 4, 2),
new Edge(2, 3, 5, 3)
);
boolean feasible = isFeasibleFlow(
edges,
vertexCount,
source,
sink
);
int flowValue = calculateFlowValue(edges, source);
System.out.println("可行流: " + feasible);
System.out.println("流值: " + flowValue);
}
private static boolean isFeasibleFlow(
List<Edge> edges,
int vertexCount,
int source,
int sink
) {
int[] balance = new int[vertexCount];
for (Edge edge : edges) {
// 先检查每条边是否违反非负约束或容量上限。
if (edge.flow() < 0 || edge.flow() > edge.capacity()) {
return false;
}
balance[edge.from()] -= edge.flow();
balance[edge.to()] += edge.flow();
}
// 普通顶点必须满足流入量等于流出量。
for (int vertex = 0; vertex < vertexCount; vertex++) {
if (
vertex != source
&& vertex != sink
&& balance[vertex] != 0
) {
return false;
}
}
return -balance[source] == balance[sink];
}
private static int calculateFlowValue(
List<Edge> edges,
int source
) {
int outgoing = 0;
int incoming = 0;
for (Edge edge : edges) {
if (edge.from() == source) {
outgoing += edge.flow();
}
if (edge.to() == source) {
incoming += edge.flow();
}
}
return outgoing - incoming;
}
}运行命令:
javac FlowNetworkDemo.java
java FlowNetworkDemo预期输出:
可行流: true
流值: 5建模边界与常见错误
真实问题中的“对象”不一定直接对应顶点。仓库、机器、人员或时间槽都可以成为顶点;道路、通信链路或可分配关系成为有向边;边容量表示可传输、可处理或可匹配的上限。
常见错误是忽略方向、把双向通行误写成一条有向边,或只检查容量而不检查中间顶点守恒。若一条关系确实允许双向传输,应建立两条方向相反、容量分别定义的边,而不是假设单条边自动双向生效。
另一个易混淆点是容量可以存在但当前流量为 0。这表示通道可用但尚未使用,并不代表边不存在。调试模型时,先逐边检查容量,再逐顶点汇总流入与流出,定位问题会更直接。
本课练习
- 将示例中的边
1 -> 3的流量改为1,运行程序并解释为什么结果变为不可行。 - 为“两个仓库向三个门店配送”建立流网络:增加超级源点连接仓库,增加超级汇点接收门店需求。验收条件是每条容量都对应一个明确业务上限。
本课总结
- 流网络使用有向边和容量描述受限传输关系。
- 可行流必须同时满足边上的容量约束和普通顶点的流量守恒。
- 流值是源点净流出量,也等于汇点净流入量,但可行流不一定是最大流。
下一课预告
下一阶段将引入剩余容量、反向边与增广路径,解释最大流算法如何在已有可行流上持续增加总流值。