分类: 算法

全局最小割:Karger’s Min Cut Algorithm

Cut in an undirected graph

Cut in an undirected graph

提到无向图的最小割问题,首先想到的就是Ford-Fulkerson算法解s-t最小割,通过Edmonds–Karp实现可以在\(O(nm^2)\)时间内解决这个问题(\(n\)为图中的顶点数,\(m\)为图中的边数)。

但是全局最小割和s-t最小割不同,并没有给定的指定的源点s和汇点t,如果通过Ford-Fulkerson算法来解这一问题,则需要枚举汇点t(共\(n-1\)),时间复杂度为\(O\left(n^2m^2\right)\)。

Can we do better?

答案是肯定的,Karger在攻读博士学位期间(Orz…)提出了非常著名的基于随机化的全局最小割算法,算法非常简单,简单到不敢相信它是正确的,算法描述如下:

  1. 在图中随机取一条边,将边的两个端点合并(contraction),同时消除所有由于合并而形成自环的边
  2. Contraction

    Contraction

  3. 重复步骤1直到图中仅剩下两个点
  4. 将最终两点之间的边作为找的割返回

这样一次运算的复杂度为\(O(m)\),我们可以看到,这样随机的过程返回的结果是不确定的,找到的割并不一定是最小的,事实上可以证明,一次运行找到最小割的概率最低为\(1/{{n}\choose{2}}\),那么,将上述算法重复执行\({{n}\choose{2}}\ln n\)次,我们可以以低于的\(1/n\)的失败概率获得最小割,这就是Karger全局最小割算法的基本思想,时间复杂度为\(O(n^2m\ln n)\)。(算法的证明很有意思,偷懒不写了哈哈,可以在参考资料中查到)

下面的C++实现仅仅是在我学习Karger算法的过程中为了理解算法而做的,因此效率很低,仅用来参考,为了简化实现,我通过暴力随机顶点对并检查的方法生成随机边,可以通过更有效的方法生成随机边来加速算法执行。

简单解释一下:对于边的contraction操作我使用并查集来模拟,非常类似于Kruskal算法的实现。

对于算法的执行过程还有一些更加高级的优化可以使得整个计算过程大大加速,不过这些优化超出了本文的范围,想了解的同学可以看这里,时间复杂度下降到了\(O(n^2\log ^3n)\)。

使用的测试数据


参考资料

  • z3

    do {
    s = rand() % n;
    vector edges = graph.edges_for_vertex(s);
    t = edges[rand() % edges.size()];
    } while (uf.find(s) == uf.find(t));

    随机选边那里优化一下并不难。选出第一个 vertex,然后直接从它的 edge list 里再随机就好了。

    • 嗯,优化的方法有很多,我只是写了一个最简单粗暴的。另外,你这种修改随机出每条边的概率不相等,感觉不是很好,这个条件在算法正确性证明中十分重要。比较好的优化应该是通过边的编号来随机,需要多占用一些空间。