数据结构与算法 / 系统课时

流网络建模

流网络建模

本课把运输、带宽或任务分配问题抽象成流网络。你将学会识别源点、汇点、容量与流量,并判断一个候选方案是否同时满足容量约束和流量守恒。

学习目标

  • 识别流网络中的源点、汇点、容量、流量和流值。
  • 使用容量约束与流量守恒判断可行流。
  • 将真实问题转换为有向图中的顶点、边和容量。

模型要素与约束

流网络是一个带容量的有向图,通常记为 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。

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;
    }
}

运行命令:

bash
javac FlowNetworkDemo.java
java FlowNetworkDemo

预期输出:

text
可行流: true
流值: 5

建模边界与常见错误

真实问题中的“对象”不一定直接对应顶点。仓库、机器、人员或时间槽都可以成为顶点;道路、通信链路或可分配关系成为有向边;边容量表示可传输、可处理或可匹配的上限。

常见错误是忽略方向、把双向通行误写成一条有向边,或只检查容量而不检查中间顶点守恒。若一条关系确实允许双向传输,应建立两条方向相反、容量分别定义的边,而不是假设单条边自动双向生效。

另一个易混淆点是容量可以存在但当前流量为 0。这表示通道可用但尚未使用,并不代表边不存在。调试模型时,先逐边检查容量,再逐顶点汇总流入与流出,定位问题会更直接。

本课练习

  1. 将示例中的边 1 -> 3 的流量改为 1,运行程序并解释为什么结果变为不可行。
  2. 为“两个仓库向三个门店配送”建立流网络:增加超级源点连接仓库,增加超级汇点接收门店需求。验收条件是每条容量都对应一个明确业务上限。

本课总结

  • 流网络使用有向边和容量描述受限传输关系。
  • 可行流必须同时满足边上的容量约束和普通顶点的流量守恒。
  • 流值是源点净流出量,也等于汇点净流入量,但可行流不一定是最大流。

下一课预告

下一阶段将引入剩余容量、反向边与增广路径,解释最大流算法如何在已有可行流上持续增加总流值。

按自己的节奏,确认真正理解。

目录与阅读设置

阅读设置

17

记录一个想法

流网络建模

0 / 10000 · 笔记保存到账号。未提交的修改会在关闭、离开或刷新后丢失。

登录哪都通