设计与分析 - 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）的边收缩。

F_strongly_bonded_supernode

步骤5

由于图中仅存在两个节点，因此边的数量是图的最终最小割。在这种情况下，给定图的最小割为2。

最小割图

原始图的最小割为 2（E → D 和 E → F）。

例子

C C++ Java Python 
#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\n", 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()
{
    // Create a graph
    Graph g(4);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    // Set seed for random number generation
    srand(time(nullptr));
    // Find the minimum cut
    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) {
        // Create a graph
        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);
        // Set seed for random number generation
        Random rand = new Random();
        rand.setSeed(System.currentTimeMillis());
        // Find the minimum cut
        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
# Create a graph
g = Graph(4)
g.addEdge(0, 1)
g.addEdge(0, 2)
g.addEdge(0, 3)
g.addEdge(1, 3)
g.addEdge(2, 3)
# Set seed for random number generation
random.seed()
# Find the minimum cut
minCut = g.kargerMinCut()
print("Minimum Cut:", minCut)

输出

Minimum Cut: 2