我不确定我是否对 mincut 有误解，但我已经使用 edmond-karps 编写了一个 mincut 算法，然后是流网络上的 BFS。
如果我告诉它从 A 到 B 做一个 mincut，它会起作用，因为剩余流 A->B = 0，所以它产生集合 {A}，切割为 A->B (1)。
但是，如果我告诉它从 B 到 A 做一个 mincut，它不会增加任何边（因为 C 没有边），所以结果集是 {C}，有一个 B->丙（2）。
在我看来，我可能会以两种方式中的一种方式误解这一点。首先，从 B 到 A 的 mincut 可能是正确的，因为只计算 B 集合中的边，而不是边（意味着 mincut 是在询问“不允许 B 连接到 A 的最小值是多少”，而不是“将图形分成 2 个分区的最小值是多少）。
或者，如果您被要求在流网络上查找 mincut（一般的 min-cut，我目前正在使用“选择任意源，尝试所有其他节点”方法），它必须要求在两个方向上的流量相等任何边缘。
"source=B, sink=A" 的“正确”最小切割为 0，因为没有边 B->A（等效地，c(B, A) = 0）；看起来您的实现可能正在回答一个不同的问题。您是否检查了 BFS 阶段中每条潜在的最短路径以确保它在接收器处结束？
（意思是 mincut 是在询问“不允许 B 连接到 A 的最小值是多少”，而不是“将图形分成 2 个分区的最小值是多少）。
是的，第一个：我们只关心从源到汇的瓶颈（max-flow min-cut theorem）。Min-cut确实将图“划分”为两部分，但还有一个额外的要求，即源和汇在不同的集合中。
（一般的最小切割，我目前正在使用“选择任意来源，尝试所有其他节点”方法）
如果您说“将所有其他节点视为汇”，这是对源外边缘的简单度数计算。
编辑：由于边缘是加权的，因此它不完全是度数计算，但它只是将边缘权重相加，无需搜索。
它必须要求在任何边缘的两个方向上都有相等的流量。
不存在这样的要求（流网络是有向图 - 任何无向边都映射到两条反平行边，对于特定的流问题，只使用一条边）。