如何借助SciPy的MaximumFlow通过最小割划分图的顶点集？

要从SciPy的MaximumFlow结果里得到最小割对应的顶点集S（包含源点）和T（包含汇点），核心是在残差网络中找出所有能从源点到达的顶点，具体步骤如下：

• 计算残差网络：残差网络的边权重 = 原始图的边权重 - 最大流的边流量，可通过graph - max_flow_object.flow直接计算（graph为输入的稀疏邻接矩阵）。
• 执行可达性分析：用广度优先搜索（BFS）或深度优先搜索（DFS）从源点出发，遍历残差网络中所有残差容量大于0的边，所有能到达的顶点构成集合S，剩余顶点即为集合T。

示例代码 #

import numpy as np
from scipy.sparse import csr_matrix
from scipy.sparse.csgraph import maximum_flow
from scipy.sparse.csgraph import breadth_first_order

# 构建示例稀疏邻接矩阵
graph = csr_matrix([
    [0, 3, 4, 0, 0],
    [0, 0, 0, 2, 0],
    [0, 0, 0, 5, 1],
    [0, 0, 0, 0, 4],
    [0, 0, 0, 0, 0]
])
source = 0
sink = 4

# 计算最大流
flow_obj = maximum_flow(graph, source, sink)

# 生成残差网络
residual_graph = graph - flow_obj.flow

# BFS遍历残差网络，获取源点可达顶点
_, predecessors = breadth_first_order(residual_graph, source, directed=True)
S = np.where(predecessors != -1)[0]
T = np.setdiff1d(np.arange(graph.shape[0]), S)

print("源点所在集合S:", S)
print("汇点所在集合T:", T)

原理说明 #

根据最大流最小割定理，最小割的容量等于最大流的值。残差网络中，S集合是所有能从源点到达的顶点，S到T的边在原始图中流量已饱和（残差容量为0），因此无法从S到达T，这组顶点划分就是对应的最小割。

内容的提问来源于stack exchange，提问作者Daniel