Karget's mincut 算法
给定一个有一个点集 V 和一个边集 G 的连通图,最小割是将点集 V 划分为两个非空集合 V1 和 V2 的一个划分,使得集合 {(u,v)|(u,v)∈G, u∈V1, v∈V2} 中的元素最少。更通俗就是说,移除最少的边,使得图被拆分。
Karger's mincut 是一个随机化算法,这个算法使用均匀选择的边收缩。当一个边收缩后,剩下的边必须保留以提高合成的新边在下一次收缩时被选中的几率。
当这个算法在有N个顶点的图上执行 N^2 次后,最小割被找到的概率接近 1-1/N
算法实现
算法
测试
生成图
测试结果