xxx 最小割的Karger算法

题目描述：
给定一个无向连通图G=(V,E)，每条边有一个权重（可以视为容量）。最小割问题要求找到一种将顶点集V划分成两个非空子集S和V\S的方法，使得连接S和V\S的边的权重之和（即割的容量）最小。Karger算法是一种简单的随机算法，用于解决此问题。

解题过程：

1. 算法核心思想
   Karger算法基于一个关键概念：随机边收缩。它通过反复随机选择一条边并将其“收缩”（即合并其两个端点），逐步减少图中的顶点数量，直到只剩下两个顶点。此时，连接这两个顶点（即两个顶点集）的边就构成了一个割。

2. 算法步骤
   a. 初始化：将原始图G复制到一个工作图G'中。
   b. 当G'中的顶点数大于2时，重复以下步骤：
   i. 在G'中均匀随机地选择一条边e（即每条边被选中的概率与其权重无关，是相等的）。
   ii. 收缩边e：将边e的两个端点u和v合并成一个新的顶点。所有原本与u或v相连的边（除了边e本身被移除外）现在都与这个新顶点相连。注意，这可能会产生自环（即新顶点连接到自己的边），自环在后续过程中需要被忽略，因为它们不会连接两个不同的顶点集。
   c. 终止：当G'中只剩下两个顶点（记为A和B）时，连接A和B的所有边的权重之和就是本次运行找到的割的容量。

3. 为什么需要多次运行
   单次运行Karger算法找到最小割的概率并不高。可以证明，对于一个有n个顶点的图，单次运行成功找到最小割的概率至少为2/(n(n-1))（大约为1/n²）。这个概率虽然低，但它是大于0的。
   因此，我们需要将整个算法独立重复运行多次（例如，运行C(n,2) * ln(n)次，或者一个足够大的常数次数），然后从所有运行结果中选取容量最小的那个割作为最终答案。通过多次运行，我们可以将以很高的概率找到真正的最小割。

4. 一个简单的例子
   考虑一个4个顶点的环：V={1,2,3,4}，边为(1,2), (2,3), (3,4), (4,1)，假设每条边权重为1。

   • 第一次运行：可能随机选择并收缩边(1,2)。现在顶点集为{1,2}, {3}, {4}。新图中，顶点{1,2}与3有边，与4也有边。接着，可能收缩边({1,2}, 3)。现在顶点集为{1,2,3}, {4}。最后，连接{1,2,3}和{4}的边是(3,4)和(4,1)（它们现在都连接着新顶点集），割的容量为2。
   • 第二次运行：可能先收缩边(1,4)。... 有可能最终得到连接{1,4}和{2,3}的割，容量也是2（边(1,2)和(3,4)）。但在这个环图中，最小割的容量是2（切断两条边）。实际上，这个图的最小割就是2。如果我们运气好，某次运行先收缩了“内部”边，最后可能得到一个容量为2的割。多次运行后，我们取到的最小值就是2。

5. 时间复杂度与总结

   • 单次运行的时间复杂度可以是O(n²)（使用邻接矩阵和适当的合并策略）或O(m)（使用邻接表和一些优化，如Union-Find的变种）。
   • 由于需要运行O(n² log n)次来保证高概率成功，总时间复杂度为O(n⁴ log n)。这看起来很高，但对于理论证明和某些特定情况（如图比较小或最小割结构简单）是有意义的。实践中，有更高效的随机化算法（如Karger-Stein算法）改进了这一基础思想。
   • 总结：Karger算法通过随机收缩边来减少顶点数，最终得到一个割。通过多次重复这一随机过程，并取最佳结果，有很高的概率可以找到无向图的最小割。