Python 算法库 networking_flow 模块详解：从 Ford-Fulkerson 到 Dinic 与 Push-Relabel 的最大流实战

本文基于 Python 算法库（All Algorithms implemented in Python）中的 networking_flow 模块，系统讲解最大流问题与最大流最小割定理的四个经典 Python 实现：Ford-Fulkerson（Edmonds-Karp）、最小割提取、Dinic 算法和 Push-Relabel（Goldberg-Tarjan）。读完本文，你将理解每类算法的核心思想与残差图机制，掌握按图结构（稀疏/稠密/含平行边）选型的方法，并能直接运行模块内自带 doctest 验证四种算法在同一经典网络上均得到最大流值 23。

一、问题定义：最大流与最小割

networking_flow/README.md 开篇即给出了本模块的统一问题定义：

给定一个带边容量的有向图、一个 source（源点）和一个 sink（汇点），在不超过任何边容量的前提下，最多能从 source 向 sink 推送多少流量？

最大流问题的典型应用场景包括：网络流量路由、人到岗位的匹配（人员-岗位二部图匹配）、调度问题、图像分割，以及一切可以表述为"通过共享网络从 A 尽可能多地转移到 B"的问题。

与最大流紧密相关的是最小割（minimum s-t cut）：从图中移除若干边使 sink 与 source 断开，其中总容量最小的边集合就是最小割。最大流最小割定理断言：最大流的值恒等于最小割的容量。这一点在本文第二节的 minimum_cut.py 中有直接的代码验证。

二、四个实现文件总览

该目录包含四个自包含（self-contained）、全类型标注、由 doctest 验证的实现：

文件	算法	图表示	复杂度
ford_fulkerson.py	Ford-Fulkerson，用 BFS 找增广路（即 Edmonds-Karp 改进）	邻接矩阵	O(V · E²)
minimum_cut.py	从 Ford-Fulkerson 遗留的残差图中提取最小割边	邻接矩阵	基于 Ford-Fulkerson
dinic.py	Dinic：BFS 建层次图 + DFS 求阻断流	邻接表	O(V² · E)；单位容量网络 O(E · √V)
push_relabel.py	Push-Relabel（Goldberg-Tarjan），最高标号选择规则	邻接表	O(V² · √E)

README 给出的选型建议是：初学者从 ford_fulkerson.py 和 minimum_cut.py 入手，因为"增广路"图像最直观；稀疏图或含平行边的图用 dinic.py，邻接表表示加上层次图批处理使其在实践中很快；稠密图用 push_relabel.py，因为它避免了反复扫描长长的增广路径。

所有文件都可以直接运行来自带测试，例如：

python networking_flow/dinic.py

三、Ford-Fulkerson：增广路与残差网络

ford_fulkerson.py 采用邻接矩阵存容量，核心算法分两步：

1. 初始流量为 0；
2. 反复在残差网络中从 source 寻找一条到 sink 的增广路，沿该路推送"瓶颈容量"（路径上残余容量最小值），并更新残差容量；找不到增广路时终止，累计值即最大流。

其中用 BFS（而非任意 DFS）选取增广路，正是 Edmonds-Karp 改进：保证每次取"边数最少"的增广路，从而得到 O(V · E²) 的确定界。

经典测试网络直接以矩阵形式给出（6 个节点，最大流为 23）：

graph = [
    [0, 16, 13, 0, 0, 0],
    [0, 0, 10, 12, 0, 0],
    [0, 4, 0, 0, 14, 0],
    [0, 0, 9, 0, 0, 20],
    [0, 0, 0, 7, 0, 4],
    [0, 0, 0, 0, 0, 0],
]

BFS 部分（ford_fulkerson.py#L20-L55）沿残差容量大于 0 的边扩展，并把遍历树记录在 parents 数组中：

def breadth_first_search(graph: list, source: int, sink: int, parents: list) -> bool:
    visited = [False] * len(graph)
    queue = []
    queue.append(source)
    visited[source] = True
    while queue:
        u = queue.pop(0)
        for ind, node in enumerate(graph[u]):
            if visited[ind] is False and node > 0:
                queue.append(ind)
                visited[ind] = True
                parents[ind] = u
    return visited[sink]

主函数 ford_fulkerson（ford_fulkerson.py#L58-L106）的关键逻辑：

while breadth_first_search(graph, source, sink, parent):
    path_flow = int(1e9)          # 路径瓶颈容量
    s = sink
    while s != source:            # 回溯路径求最小残量
        path_flow = min(path_flow, graph[parent[s]][s])
        s = parent[s]

    max_flow += path_flow
    v = sink
    while v != source:            # 更新残差网络
        u = parent[v]
        graph[u][v] -= path_flow
        graph[v][u] += path_flow # 反向边获得回退容量
        v = parent[v]

两点值得注意：

• 反向边更新 graph[v][u] += path_flow 是残差网络（residual graph）的核心——它允许后续增广路"撤销"之前走过的流量，这是 Ford-Fulkerson 正确性的关键；
• 源码 docstring 明确警告：CAUTION: This function changes the given graph，即该函数会就地修改传入的邻接矩阵。doctest 中也用 IndexError 用例验证了对越界 sink 的直接报错。

运行方式：

python networking_flow/ford_fulkerson.py   # 先执行 doctest，再打印 23

四、最小割：从残差图读出最大流最小割

minimum_cut.py 的 docstring 对定理的表述值得完整引用：

最大流最小割定理说，源到汇的最大流值等于最小 s-t 割中边的总容量——即"移除这些边即可断开汇与源、且总代价最小"的边集。本模块找出这些割边：先运行 Ford-Fulkerson 构建残差图，然后报告每一条从"仍可从源到达的顶点"指向"不可达顶点"的原始边。

mincut 函数的实现分两阶段（minimum_cut.py#L50-L94）：

阶段一：在一份内部拷贝上完整跑 Ford-Fulkerson（注意：residual = [row[:] for row in graph] 保证输入矩阵不被修改，与 ford_fulkerson.py 的就地修改形成对照），得到终止时的残差图。

阶段二：按定义枚举原图边——若 graph[i][j] > 0 且 residual[i][j] == 0，则边 (i, j) 属于最小割：

for i in range(len(graph)):
    for j in range(len(graph[0])):
        if graph[i][j] > 0 and residual[i][j] == 0:
            res.append((i, j))

直觉上：算法终止时从源出发在残差图上不可达的顶点集合构成割的一侧；任何"源侧有容量但残差已耗尽、且指向汇侧"的边，正是被流量完全堵死的那些边。

doctest 直接验证了定理本身（minimum_cut.py#L57-L63）：

>>> mincut(test_graph, source=0, sink=5)
[(1, 3), (4, 3), (4, 5)]

# 割边容量之和等于最大流值（本例为 23）：
>>> sum(test_graph[u][v] for u, v in mincut(test_graph, 0, 5))
23

三条割边 12 + 7 + 4 恰好等于最大流 23，与 ford_fulkerson.py 的输出相互印证。

五、Dinic 算法：层次图 + 阻断流

dinic.py 是四个实现中工程化程度最高的：Dinic 类、全类型标注、参数校验完备。它把增广路按长度分组处理——每一轮先 BFS 建层次图（level graph），再一次性在层次图上 DFS 求阻断流（blocking flow），从而比逐条找路的 Edmonds-Karp 获得更优的最坏界：O(V² · E)，单位容量网络上为 O(E · √V)（dinic.py#L10-L11）。

5.1 邻接表 + 成对残差边

与矩阵版不同，Dinic 用邻接表存图（dinic.py#L57-L89）：每条边存为 [destination, residual_capacity]，且边 i 与其反向边 i ^ 1 永远成对创建：

def add_edge(self, source: int, destination: int, capacity: int) -> None:
    if capacity < 0:
        raise ValueError("capacity must be non-negative")
    if not (0 <= source < self.size and 0 <= destination < self.size):
        raise ValueError("vertex out of range")
    self.graph[source].append(len(self.edges))
    self.edges.append([destination, capacity])
    self.graph[destination].append(len(self.edges))
    self.edges.append([source, 0])  # 反向边初始饱和（残量为 0）

这个"成对残差边"设计带来两个实际好处（doctest 均有验证）：

• 支持平行边：同一顶点对上多次调用 add_edge(0, 1, 3) 和 add_edge(0, 1, 5)，容量自然累加，max_flow(0, 1) 返回 8；
• 稀疏图高效：遍历只触及实际存在的边，而不是 O(V) 的矩阵行。

5.2 三层结构：BFS 分层 → DFS 推流 → 循环

max_flow 的主循环（dinic.py#L130-L160）：

flow = 0
level = self._build_level_graph(source)
while level[sink] != -1:                    # 汇点不可达时终止
    progress = [0] * self.size              # 当前弧（current-arc）优化
    while True:
        pushed = self._send_flow(source, infinity, sink, level, progress)
        if pushed == 0:                     # 阻断流已求出
            break
        flow += pushed
    level = self._build_level_graph(source) # 重建层次图，进入下一轮

• _build_level_graph（dinic.py#L91-L103）：标准 BFS，沿残量 > 0 的边给顶点标层号，不可达点为 -1；
• _send_flow（dinic.py#L105-L128）：DFS 只允许沿"层号恰好 +1"的边推流，并用 progress 数组（当前弧优化）跳过已耗尽的边，避免重复扫描；推流成功时同步更新 edges[edge_index ^ 1][1] += flow 反向残量。

doctest 覆盖了三类场景：经典 6 节点网络得 23、无出边的源点得 0、平行边累加得 8，以及 source == sink 抛 ValueError。

python networking_flow/dinic.py

六、Push-Relabel：预流、压流与重新标号

push_relabel.py 代表与增广路方法根本不同的范式（模块 docstring 明确指出）：它不逐条寻找源到汇的路径，而是维护一个预流（preflow）——允许中间顶点暂时"接收多于发出的流量"（即存在 excess 过剩量）。每个活跃顶点要么 push（压流）：把过剩量沿"高度恰好低 1"的边推给邻居；要么 relabel（重新标号）：抬高自身高度使压流成为可能。当除源、汇外所有顶点 excess 归零时，预流即为最大流。

max_flow 的实现（push_relabel.py#L90-L136）展示了完整的算法骨架：

height = [0] * self.size
excess = [0] * self.size
height[source] = self.size      # 源点标号设为 |V|

# 阶段 1：饱和所有从源出发的边，建立初始预流
for edge_index in self.graph[source]:
    destination, residual = self.edges[edge_index]
    if residual > 0:
        self.edges[edge_index][1] -= residual
        self.edges[edge_index ^ 1][1] += residual
        excess[destination] += residual
        excess[source] -= residual

active = [v for v in range(self.size)
          if v not in (source, sink) and excess[v] > 0]

while active:
    u = max(active, key=lambda v: height[v])   # 最高标号选择规则
    if not self._discharge(u, height):         # 无可压边 → 重新标号
        min_height = min(
            height[self.edges[i][0]]
            for i in self.graph[u]
            if self.edges[i][1] > 0
        )
        height[u] = min_height + 1             # 抬到最低可用邻居之上
    self._apply_pushes(u, height, excess)
    active = [v for v in range(self.size)
              if v not in (source, sink) and excess[v] > 0]

return excess[sink]

几个关键细节：

• 高度函数（height）约束：_discharge（push_relabel.py#L138-L143）判定"许可边"——残量 > 0 且 height[dest] == height[u] - 1。这是 push-relabel 的可行性不变量；
• relabel 的精确取值：抬到"最低可用邻居 + 1"，保证下次立即有许可边可压；
• 最高标号选择规则（max(active, key=...)）：始终处理标号最大的活跃顶点，这是 README 给出 O(V² · √E) 界的前提，也是其在稠密图上快于增广路方法的原因——它从不"回溯扫描"长路径。

同样地，doctest 用经典 6 节点网络验证结果为 23，并覆盖了平行边（3+5=8）、孤立汇点（0）与 source == sink 报错。

七、四个实现的对照与使用建议

四个实现计算的是同一个最大流值，差别在速度、图表示与 API 形态：

维度	ford_fulkerson.py / minimum_cut.py	dinic.py	push_relabel.py
图表示	邻接矩阵	邻接表（成对残差边）	邻接表（成对残差边）
平行边支持	否（矩阵单元被覆盖）	是	是
是否修改输入	ford_fulkerson 修改；mincut 不修改	不适用（对象式 API）	不适用（对象式 API）
复杂度	O(V · E²)	O(V² · E)，单位容量 O(E · √V)	最高标号：O(V² · √E)
适用场景	教学理解增广路/残差图	稀疏图、一般竞赛场景	稠密图

选型建议（直接继承自 networking_flow/README.md 的 "Which one should I use?"）：

• 刚入门：读 ford_fulkerson.py + minimum_cut.py，建立"增广路 + 残差图 + 割"的直觉；
• 稀疏图 / 有平行边：用 Dinic 类；
• 稠密图：用 PushRelabel 类。

调用形态上，两个类式实现完全同构，都是"先 add_edge，后 max_flow"：

from networking_flow.dinic import Dinic   # 或 PushRelabel

g = Dinic(6)
capacities = {
    (0, 1): 16, (0, 2): 13, (1, 2): 10, (1, 3): 12,
    (2, 1): 4,  (2, 4): 14, (3, 2): 9,  (3, 5): 20,
    (4, 3): 7,  (4, 5): 4,
}
for (u, v), cap in capacities.items():
    g.add_edge(u, v, cap)
print(g.max_flow(0, 5))  # -> 23

八、验证方式：每个文件都是自带 doctest 的独立程序

该模块的统一质量约定是"每个文件自包含、全类型标注、doctest 验证"。四个文件的 __main__ 块均调用 doctest.testmod()，因此：

python networking_flow/ford_fulkerson.py
python networking_flow/minimum_cut.py
python networking_flow/dinic.py
python networking_flow/push_relabel.py

逐条执行各自的全部 doctest。经典 6 节点网络（0 为源、5 为汇）在四个实现中均得到 23，且 minimum_cut.py 额外验证了割边 [(1, 3), (4, 3), (4, 5)] 的容量和等于 23——用可运行的代码把"最大流最小割定理"钉死在同一个数字上。