使用JGraphT的EdmondsKarpMFImpl获取最小割全部参与边的问题

问题原因澄清 #

你调用EdmondsKarpMFImpl.getCutEdges()返回1->2和1->7是符合有向图s-t最小割的标准定义的：
s-t最小割是将图顶点划分为两个不相交集合S（包含源点1）、T（包含汇点5），割边集为所有起点在S、终点在T的有向边，最小割即该边集总容量最小的划分。你当前的场景下，取S={1}、T=其余所有顶点时，割边集总容量为2，是全局最小值，因此API返回结果符合算法设计。

你预期的7条边总容量为7，远大于2，不属于标准最小割的范畴，本质是所有位于源点1到汇点5的简单路径上的边。

提示：JGraphT最大流实现默认取边的weight属性作为容量，如果你的边实际容量为10、权重仅为业务属性，构造EdmondsKarpMFImpl时需要传入自定义的Function<E, Double>容量映射，避免计算结果不符合预期。

目标边集获取方法 #

如果需要拿到你预期的所有源到汇路径上的边，可以通过两次广度/深度优先遍历实现：

1. 第一次遍历：在原图上从源点1出发做BFS/DFS，记录所有1可达的节点集合reachableFromSource
2. 第二次遍历：将原图所有边反向，从汇点5出发做BFS/DFS，记录所有能到达5的节点集合canReachSink
3. 遍历原图所有边，筛选出满足「起点属于reachableFromSource∩canReachSink、终点也属于reachableFromSource∩canReachSink」的边，即为你需要的集合。

示例代码 #

// 第一步：获取源点可达集合
Set<Integer> reachableFromSource = new HashSet<>();
BreadthFirstIterator<Integer, MyDefaultWeightedEdge> bfsSource = new BreadthFirstIterator<>(exGraph3, 1);
while (bfsSource.hasNext()) {
    reachableFromSource.add(bfsSource.next());
}

// 第二步：构建反向图，获取可到达汇点的集合
Graph<Integer, MyDefaultWeightedEdge> reversedGraph = new EdgeReversedGraph<>(exGraph3);
Set<Integer> canReachSink = new HashSet<>();
BreadthFirstIterator<Integer, MyDefaultWeightedEdge> bfsSink = new BreadthFirstIterator<>(reversedGraph, 5);
while (bfsSink.hasNext()) {
    canReachSink.add(bfsSink.next());
}

// 第三步：求交集，筛选符合条件的边
Set<Integer> commonNodes = new HashSet<>(reachableFromSource);
commonNodes.retainAll(canReachSink);
Set<MyDefaultWeightedEdge> targetEdges = new HashSet<>();
for (MyDefaultWeightedEdge edge : exGraph3.edgeSet()) {
    Integer u = exGraph3.getEdgeSource(edge);
    Integer v = exGraph3.getEdgeTarget(edge);
    if (commonNodes.contains(u) && commonNodes.contains(v)) {
        targetEdges.add(edge);
    }
}

如果你需要的是所有属于任意最小割的边 #

如果你的需求是获取所有可能出现在任意一个s-t最小割中的边，可通过残量网络遍历实现：

1. 跑完最大流后，获取残量网络
2. 从源点出发在残量网络中仅走剩余容量>0的边，得到集合S
3. 从汇点出发在反向残量网络中仅走剩余容量>0的边，得到集合T
4. 原图中满足u∈S且v∈T的边即为目标边。

内容的提问来源于stack exchange，提问作者Gábor Szegedi