借鉴：http://blog.kongfy.com/2015/02/kargermincut/
提到无向图的最小割问题，首先想到的就是Ford-Fulkerson算法解s-t最小割，通过Edmonds–Karp实现可以在O(nm2)时间内解决这个问题（n为图中的顶点数，m为图中的边数）。
但是全局最小割和s-t最小割不同，并没有给定的指定的源点s和汇点t，如果通过Ford-Fulkerson算法来解这一问题，则需要枚举汇点t（共n−1），时间复杂度为O(n2m2)。
Can we do better?
答案是肯定的，Karger在攻读博士学位期间（Orz…）提出了非常著名的基于随机化的全局最小割算法，算法非常简单，简单到不敢相信它是正确的，算法描述如下：
-
- 在图中随机取一条边，将边的两个端点合并（contraction），同时消除所有由于合并而形成自环的边
Contraction
版权声明：本文内容由互联网用户自发贡献，该文观点仅代表作者本人。本站仅提供信息存储空间服务，不拥有所有权，不承担相关法律责任。如发现本站有涉嫌侵权/违法违规的内容，请联系我们，一经查实，本站将立刻删除。
如需转载请保留出处：https://51itzy.com/kjqy/57554.html