连通二分图删除最少边生成不连通分量的高效算法求荐

你要解决的问题本质是无向图的全局最小边割，完全不需要用到需要提前指定k值的min k-cut算法，前者的复杂度和实现难度都远低于后者，刚好匹配你的需求：全局最小边割的定义就是将连通图分割为至少两个非空连通分量所需删除的最少边数，不需要提前指定最终的连通分量数量。

针对你是二分图的场景，可以按优先级选择以下高效算法：

• 优先方案（适配无权二分图，绝大多数场景最优）：利用最大流最小割定理实现
  二分图的全局最小割可以转化为最大流求解：任选二分图左部任意一个点作为源点s，枚举右部所有点作为汇点t，用Dinic算法计算s-t的最大流，所有计算结果中的最小值就是你要的最小删除边数。Dinic在单位容量的无权二分图上时间复杂度为O(E*sqrt(V))，性能非常高，足够应对万级顶点规模的图。
• 备选方案（适配带权二分图/通用场景）：Stoer-Wagner算法
  这是无向图全局最小割的经典通用算法，不需要利用二分图特性也能直接运行，普通实现时间复杂度为O(n³)，优先队列优化后可以达到O(nm + n²logn)，适合带权二分图或者两边顶点规模都很大的场景。

注意：完全不需要调研任何k-cut相关的实现，你的需求用全局最小割就能100%覆盖，计算成本远低于k-cut类算法。

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