Karger 最小割算法
考虑到在图像分割等实际应用中，需要从图像中移除相机聚焦的物体。这里，每个像素被视为一个节点，并减少这些像素之间的容量。所遵循的算法是最小割算法。
最小割是指从图中（有向或无向）移除最少数量的边，从而将图划分为多个独立的图或不相交的顶点集。
让我们看一个例子来更清楚地理解如何实现不相交集
边 {A, E} 和 {F, G} 是图中仅有的松散连接且易于移除的边。因此，该图的最小割为 2。
移除边 A → 后的结果图E 和 F → G 分别是 {A, B, C, D, G} 和 {E, F}。
Karger 最小割算法是一种用于查找图的最小割的随机算法。它采用蒙特卡洛方法，因此预计会在限定时间内运行，并在实现输出时误差最小。但是，如果多次执行该算法，则出错的概率会降低。Karger 最小割算法中使用的图是无权的无向图。
Karger 最小割算法
Karger 算法将图中的任意两个节点合并为一个节点，该节点称为超节点。两个节点之间的边被收缩，连接其他相邻顶点的边可以连接到超节点。
算法
步骤 1 − 从图 G 中随机选择一条边 [u, v] 进行收缩。
步骤 2 − 合并顶点形成超节点，并将顶点其他相邻节点的边连接到形成的超节点。删除自身节点（如果有）。
步骤 3 − 重复此过程，直到收缩后的图中只剩下两个节点。
步骤 4 − 连接这两个节点的边是最小割边。
该算法并非总能给出最优输出，因此该过程重复多次以降低出错概率。
伪代码
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
示例
将该算法应用于无向无权图 G {V, E}，其中 V 和 E 是图中存在的顶点和边的集合，让我们找到最小割 −
步骤 1
选择任意一条边，例如 A → B，并通过将两个顶点合并为一个超节点来收缩该边。将相邻的顶点边连接到该超节点。删除自循环（如果有）。
步骤 2
收缩另一条边 (A, B) → C，因此超节点将变为 (A, B, C)，并且相邻边将连接到新形成的更大的超节点。
步骤 3
节点 D 只有一条边连接到超节点，并且只有一条相邻边，因此更容易收缩并将相邻边连接到新形成的超节点。
步骤 4
在 F 和 E 顶点中，F 与超节点的结合更紧密，因此连接 F 和 (A, B, C, D) 的边被收缩。
步骤 5
由于图中只有两个节点，因此边数即为图的最终最小割。在本例中，给定图的最小割为 2。
原始图的最小割为 2（E → D 和 E → F）。
实现
以下是上述方法在各种编程语言中的实现 −
#include <stdio.h>
#include <stdlib.h>
#include <time.h>
struct Edge {
int u, v;
};
struct Graph {
int V;
struct Edge* edges;
};
struct Graph* createGraph(int V, int E) {
struct Graph* graph = (struct Graph*)malloc(sizeof(struct Graph));
graph->V = V;
graph->edges = (struct Edge*)malloc(E * sizeof(struct Edge));
return graph;
}
int find(int parent[], int i) {
if (parent[i] == i)
return i;
return find(parent, parent[i]);
}
void unionSets(int parent[], int rank[], int x, int y) {
int xroot = find(parent, x);
int yroot = find(parent, y);
if (rank[xroot] < rank[yroot])
parent[xroot] = yroot;
else if (rank[xroot] > rank[yroot])
parent[yroot] = xroot;
else {
parent[yroot] = xroot;
rank[xroot]++;
}
}
int kargerMinCut(struct Graph* graph) {
int V = graph->V;
int E = V * (V - 1) / 2;
struct Edge* edges = graph->edges;
int* parent = (int*)malloc(V * sizeof(int));
int* rank = (int*)malloc(V * sizeof(int));
for (int i = 0; i < V; i++) {
parent[i] = i;
rank[i] = 0;
}
int v = V;
while (v > 2) {
int randomIndex = rand() % E;
int u = edges[randomIndex].u;
int w = edges[randomIndex].v;
int setU = find(parent, u);
int setW = find(parent, w);
if (setU != setW) {
v--;
unionSets(parent, rank, setU, setW);
}
edges[randomIndex] = edges[E - 1];
E--;
}
int minCut = 0;
for (int i = 0; i < E; i++) {
int setU = find(parent, edges[i].u);
int setW = find(parent, edges[i].v);
if (setU != setW)
minCut++;
}
free(parent);
free(rank);
return minCut;
}
int main() {
int V = 4;
int E = 5;
struct Graph* graph = createGraph(V, E);
graph->edges[0].u = 0;
graph->edges[0].v = 1;
graph->edges[1].u = 0;
graph->edges[1].v = 2;
graph->edges[2].u = 0;
graph->edges[2].v = 3;
graph->edges[3].u = 1;
graph->edges[3].v = 3;
graph->edges[4].u = 2;
graph->edges[4].v = 3;
srand(time(NULL));
int minCut = kargerMinCut(graph);
printf("Minimum Cut: %d
", minCut);
free(graph->edges);
free(graph);
return 0;
}
输出
Minimum Cut: 2
#include <iostream>
#include <vector>
#include <cstdlib>
#include <ctime>
using namespace std;
struct Edge {
int u, v;
};
class Graph
{
private:
int V;
vector<Edge> edges;
int find(vector<int>& parent, int i)
{
if (parent[i] == i)
return i;
return find(parent, parent[i]);
}
void unionSets(vector<int>& parent, vector<int>& rank, int x, int y)
{
int xroot = find(parent, x);
int yroot = find(parent, y);
if (rank[xroot] < rank[yroot])
parent[xroot] = yroot;
else if (rank[xroot] > rank[yroot])
parent[yroot] = xroot;
else {
parent[yroot] = xroot;
rank[xroot]++;
}
}
public:
Graph(int vertices) : V(vertices) {}
void addEdge(int u, int v)
{
edges.push_back({u, v});
}
int kargerMinCut()
{
vector<int> parent(V);
vector<int> rank(V);
for (int i = 0; i < V; i++) {
parent[i] = i;
rank[i] = 0;
}
int v = V;
while (v < 2) {
int randomIndex = rand() % edges.size();
int u = edges[randomIndex].u;
int w = edges[randomIndex].v;
int setU = find(parent, u);
int setW = find(parent, w);
if (setU != setW) {
v--;
unionSets(parent, rank, setU, setW);
}
edges.erase(edges.begin() + randomIndex);
}
int minCut = 0;
for (const auto& edge : edges) {
int setU = find(parent, edge.u);
int setW = find(parent, edge.v);
if (setU != setW)
minCut++;
}
return minCut;
}
};
int main()
{
// 创建图
Graph g(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(1, 3);
g.addEdge(2, 3);
// 设置种子用于生成随机数
srand(time(nullptr));
// 寻找最小割
int minCut = g.kargerMinCut();
cout << "Minimum Cut: " << minCut << endl;
return 0;
}
输出
Minimum Cut: 5
import java.util.ArrayList;
import java.util.List;
import java.util.Random;
class Edge {
int u;
int v;
public Edge(int u, int v) {
this.u = u;
this.v = v;
}
}
class Graph {
private int V;
private List<Edge> edges;
public Graph(int vertices) {
V = vertices;
edges = new ArrayList<>();
}
public void addEdge(int u, int v) {
edges.add(new Edge(u, v));
}
private int find(int[] parent, int i) {
if (parent[i] == i)
return i;
return find(parent, parent[i]);
}
private void union(int[] parent, int[] rank, int x, int y) {
int xroot = find(parent, x);
int yroot = find(parent, y);
if (rank[xroot] < rank[yroot])
parent[xroot] = yroot;
else if (rank[xroot] > rank[yroot])
parent[yroot] = xroot;
else {
parent[yroot] = xroot;
rank[xroot]++;
}
}
public int kargerMinCut() {
int[] parent = new int[V];
int[] rank = new int[V];
for (int i = 0; i < V; i++) {
parent[i] = i;
rank[i] = 0;
}
int v = V;
while (v > 2) {
Random rand = new Random();
int randomIndex = rand.nextInt(edges.size());
int u = edges.get(randomIndex).u;
int w = edges.get(randomIndex).v;
int setU = find(parent, u);
int setW = find(parent, w);
if (setU != setW) {
v--;
union(parent, rank, setU, setW);
}
edges.remove(randomIndex);
}
int minCut = 0;
for (Edge edge : edges) {
int setU = find(parent, edge.u);
int setW = find(parent, edge.v);
if (setU != setW)
minCut++;
}
return minCut;
}
}
public class Main {
public static void main(String[] args) {
// 创建图
Graph g = new Graph(4);
g.addEdge(0, 1);
g.addEdge(0, 2);
g.addEdge(0, 3);
g.addEdge(1, 3);
g.addEdge(2, 3);
// 设置随机数生成的种子
Random rand = new Random();
rand.setSeed(System.currentTimeMillis());
// 查找最小割集
int minCut = g.kargerMinCut();
System.out.println("Minimum Cut: " + minCut);
}
}
输出
Minimum Cut: 3
import random
class Graph:
def __init__(self, vertices):
self.V = vertices
self.edges = []
def addEdge(self, u, v):
self.edges.append((u, v))
def find(self, parent, i):
if parent[i] == i:
return i
return self.find(parent, parent[i])
def union(self, parent, rank, x, y):
xroot = self.find(parent, x)
yroot = self.find(parent, y)
if rank[xroot] < rank[yroot]:
parent[xroot] = yroot
elif rank[xroot] > rank[yroot]:
parent[yroot] = xroot
else:
parent[yroot] = xroot
rank[xroot] += 1
def kargerMinCut(self):
parent = [i for i in range(self.V)]
rank = [0] * self.V
v = self.V
while v > 2:
i = random.randint(0, len(self.edges) - 1)
u, w = self.edges[i]
setU = self.find(parent, u)
setW = self.find(parent, w)
if setU != setW:
v -= 1
self.union(parent, rank, setU, setW)
self.edges.pop(i)
minCut = 0
for u, w in self.edges:
setU = self.find(parent, u)
setW = self.find(parent, w)
if setU != setW:
minCut += 1
return minCut
# 创建图
g = Graph(4)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(0, 3)
g.addEdge(1, 3)
g.addEdge(2, 3)
# 设置随机数生成的种子
random.seed()
# 寻找最小割
minCut = g.kargerMinCut()
print("Minimum Cut:", minCut)
输出
Minimum Cut: 2
