Karger最小割算法

Table of content
上一页
下一页

考虑现实世界的应用，例如图像分割，其中需要从图像中去除相机聚焦的对象。在这里，每个像素都被视为一个节点，并且这些像素之间的容量被减少。遵循的算法是最小割算法。

最小割是指从图（有向或无向）中移除最少数量的边，使得图被分割成多个单独的图或不相交的顶点集。

让我们来看一个例子，以便更清楚地理解所获得的不相交集

disjoint_sets

边{A, E}和{F, G}是唯一容易从图中移除的松散连接的边。因此，该图的最小割为2。

minimum_cut

移除边A→E和F→G后，得到的图是{A, B, C, D, G}和{E, F}。

removing_edges

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分别是图中存在的顶点和边的集合，让我们找到最小割：

undirected_unweighted

步骤1

选择任意一条边，例如A→B，并通过将两个顶点合并成一个超节点来收缩该边。将相邻顶点的边连接到超节点。删除任何自环。

merging_two_vertices

步骤2

收缩另一条边(A, B)→C，因此超节点将变成(A, B, C)，并且相邻边连接到新形成的更大的超节点。

bigger_supernode

步骤3

节点D只有一条边连接到超节点和一条相邻边，因此更容易收缩并将相邻边连接到新形成的超节点。

new_supernode_formed

步骤4

在F和E顶点中，F与超节点的连接更强，因此收缩连接F和(A, B, C, D)的边。

F_strongly_bonded_supernode

步骤5

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

minimum_cut_graph

原始图的最小割为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
打印页面
上一页
下一页
广告
© . All rights reserved.