Data Structures Algorithms 简明教程

Karger’s Minimum Cut Algorithm

考虑到像图像分割这样的实际应用，其中需要从图像中移除摄像头聚焦的对象。在这里，每个像素被视为一个节点，这些像素之间的容量被减小。遵循的算法是最小割算法。

Minimum Cut 是在图（有向或无向）中移除最少数量的边，从而将图划分为多个独立的图或不相交的顶点集。

让我们看一个示例，以更清晰地理解达到的不相交集

边 {A, E} 和 {F, G} 是唯一松散粘合，可以轻松地从图中移除的边。因此，图的最小割为 2。

在移除边 A → E 和 F → G 之后，生成的图是 {A, B, C, D, G} 和 {E, F}。

Karger’s Minimum Cut 算法是一个随机算法，用于找到图的最小割。它使用蒙特卡罗方法，因此预期在时间限制内运行，并在获得输出时将误差最小化。但是，如果执行该算法多次，则误差的可能性会降低。karger 最小割算法中使用的图是没有权重的无向图。

Karger’s Minimum Cut Algorithm

karger 的算法将图中的任意两个节点合并成一个节点，称为超级节点。两个节点之间的边收缩，并且连接其他相邻顶点的其他边可以连接到超级节点。

Algorithm

Step 1 − 从图 G 中选择任意一条随机边 [u, v] 进行收缩。

Step 2 − 合并这些顶点以形成一个超级节点，并将这些顶点的其他相邻节点的边连接到已形成的超级节点。如果存在，则删除自结点。

Step 3 − 重复此过程，直到收缩的图中仅剩两个节点。

Step 4 − 连接这两个节点的边是最小割边。

该算法并不总能给出最优输出，因此重复此过程多次以降低错误概率。

Pseudocode

Kargers_MinCut(edge, V, E):
   v = V
   while(v > 2):
      i=Random integer in the range [0, E-1]
      s1=find(edge[i].u)
      s2=find(edge[i].v)
      if(s1 != s2):
         v = v-1
         union(u, v)
   mincut=0
   for(i in the range 0 to E-1):
      s1=find(edge[i].u)
      s2=find(edge[i].v)
      if(s1 != s2):
         mincut = mincut + 1
   return mincut