xxx 最小割的 Karger 算法

问题描述
给定一个无向连通图 G=(V,E)，每条边有一个非负权重（或容量），最小割问题是找到一组边，删除后会使图变得不连通，且这组边的权重之和最小。Karger 算法是一种随机算法，通过反复收缩边来求解最小割，特别适合处理边权相等的情况。

算法步骤

1. 初始化

   • 将原图 G 复制到当前图 G' 中
   • 记录当前最小割值 min_cut = ∞

2. 重复执行以下过程足够多次（通常为 n² log n 次）：
   a. 随机边收缩

   • 在 G' 中随机选择一条边 e=(u,v)，要求 u≠v
   • 将顶点 u 和 v 合并为一个新顶点
   • 将原来与 u 或 v 相连的边都连接到新顶点
   • 删除自环（连接同一顶点的边）

   b. 终止条件检查

   • 当 G' 中只剩下 2 个顶点时停止收缩
   • 此时连接这两个顶点的边的权重和就是本次运行的割值

   c. 更新最小值

   • 如果本次割值小于 min_cut，则更新 min_cut

3. 输出结果

   • 返回 min_cut 作为最小割的权重和

关键细节说明

• 收缩操作：合并两个顶点时，新顶点继承原顶点的所有连接，但删除两个原顶点之间的所有边（自环）
• 随机选择：每次均匀随机选择一条有效边（连接不同顶点的边）
• 成功概率：单次运行找到最小割的概率至少为 1/(n choose 2)，因此需要重复 O(n² log n) 次来保证高成功率
• 时间复杂度：单次运行 O(n²)，总复杂度 O(n⁴ log n)，可用邻接表优化到 O(n² log n)

示例演示
考虑 4 个顶点的环图：1-2-3-4-1

• 随机选择边 (1,2) 收缩：新顶点 (12) 连接 3 和 4
• 随机选择边 (3,4) 收缩：新顶点 (34) 连接 (12)
• 最后剩下顶点 (12) 和 (34)，割值为 2（两条边）
  经过多次运行，会找到最小割值 2

算法特点

• 简单易实现，适合教学和理解最小割概念
• 随机性算法，可能失败但可重复运行提高成功率
• 对稠密图效果较好，是首个用于最小割的随机算法