Karger's Min Cut Algorithm

function kargerMinCut(graph) {
    // Create a deep copy of the graph
    const workingGraph = JSON.parse(JSON.stringify(graph));
    
    // Keep track of which original vertices are in each contracted vertex
    const vertexMap = {};
    for (const v in graph) {
        vertexMap[v] = [v];
    }
    
    // Continue until only 2 vertices remain
    while (Object.keys(workingGraph).length > 2) {
        // Select a random vertex
        const vertices = Object.keys(workingGraph);
        const u = vertices[Math.floor(Math.random() * vertices.length)];
        
        // Skip if no edges
        if (workingGraph[u].length === 0) continue;
        
        // Select a random neighbor
        const v = workingGraph[u][Math.floor(Math.random() * workingGraph[u].length)];
        
        // Merge v into u
        vertexMap[u] = [...vertexMap[u], ...vertexMap[v]];
        
        // Redirect edges
        for (const neighbor of workingGraph[v]) {
            if (neighbor !== u) { // Avoid self-loops
                workingGraph[u].push(neighbor);
                
                // Replace v with u in neighbor's edge list
                workingGraph[neighbor] = workingGraph[neighbor].map(x => x === v ? u : x);
            }
        }
        
        // Remove v
        delete workingGraph[v];
        delete vertexMap[v];
        
        // Remove self-loops
        workingGraph[u] = workingGraph[u].filter(w => w !== u);
    }
    
    // Return the number of edges between the two remaining vertices
    const vertices = Object.keys(workingGraph);
    if (vertices.length < 2) return 0;
    return workingGraph[vertices[0]].length;
}

function findMinCut(graph, iterations = 100) {
    let minCut = Infinity;
    for (let i = 0; i < iterations; i++) {
        const cut = kargerMinCut(graph);
        minCut = Math.min(minCut, cut);
    }
    return minCut;
}

// Example usage
const exampleGraph = {
    '0': ['1', '2', '3'],
    '1': ['0', '3'],
    '2': ['0', '3', '4'],
    '3': ['0', '1', '2', '4'],
    '4': ['2', '3']
};

const minCut = findMinCut(exampleGraph, 100);
console.log(`Minimum cut value: ${minCut}`);

#include 
#include 
#include 
#include 
#include 
#include 
#include 

using namespace std;

// Structure to represent a graph
struct Graph {
    int V;  // Number of vertices
    vector> adj;  // Adjacency list
    
    // Constructor
    Graph(int vertices) : V(vertices) {
        adj.resize(V);
    }
    
    // Add an edge
    void addEdge(int u, int v) {
        adj[u].push_back(v);
        adj[v].push_back(u);
    }
    
    // Create a copy of the graph
    Graph copy() {
        Graph g(V);
        for (int i = 0; i < V; i++) {
            g.adj[i] = adj[i];
        }
        return g;
    }
};

// Function to find the minimum cut using Karger's algorithm
int kargerMinCut(Graph& g) {
    // Random number generator
    random_device rd;
    mt19937 gen(rd());
    
    // Create a working copy
    Graph working = g.copy();
    
    // Keep track of which vertices have been contracted
    vector> contracted(g.V);
    for (int i = 0; i < g.V; i++) {
        contracted[i].push_back(i);
    }
    
    // Continue until only 2 vertices remain
    int remainingVertices = g.V;
    while (remainingVertices > 2) {
        // Pick a random edge
        int u = uniform_int_distribution<>(0, remainingVertices - 1)(gen);
        
        // Skip if no edges
        if (working.adj[u].empty()) continue;
        
        int v = working.adj[u][uniform_int_distribution<>(0, working.adj[u].size() - 1)(gen)];
        
        // Contract edge (u, v)
        // Merge v's edges into u
        for (int neighbor : working.adj[v]) {
            if (neighbor != u) {  // Avoid self-loops
                working.adj[u].push_back(neighbor);
                
                // Replace v with u in neighbor's adjacency list
                replace(working.adj[neighbor].begin(), working.adj[neighbor].end(), v, u);
            }
        }
        
        // Remove all edges to v
        for (int i = 0; i < remainingVertices; i++) {
            working.adj[i].erase(
                remove(working.adj[i].begin(), working.adj[i].end(), v),
                working.adj[i].end()
            );
        }
        
        // Remove self-loops
        working.adj[u].erase(
            remove(working.adj[u].begin(), working.adj[u].end(), u),
            working.adj[u].end()
        );
        
        // Move the last vertex to position v and decrease count
        if (v != remainingVertices - 1) {
            working.adj[v] = working.adj[remainingVertices - 1];
            
            // Update references to the moved vertex
            for (int i = 0; i < remainingVertices; i++) {
                replace(working.adj[i].begin(), working.adj[i].end(), remainingVertices - 1, v);
            }
        }
        
        remainingVertices--;
    }
    
    // Return the number of edges between the two remaining vertices
    return working.adj[0].size();
}

// Function to find the minimum cut by running Karger's algorithm multiple times
int findMinCut(Graph& g, int iterations = 100) {
    int minCut = INT_MAX;
    for (int i = 0; i < iterations; i++) {
        int cut = kargerMinCut(g);
        minCut = min(minCut, cut);
    }
    return minCut;
}

int main() {
    // Example graph
    Graph g(5);
    g.addEdge(0, 1);
    g.addEdge(0, 2);
    g.addEdge(0, 3);
    g.addEdge(1, 3);
    g.addEdge(2, 3);
    g.addEdge(2, 4);
    g.addEdge(3, 4);
    
    int minCut = findMinCut(g, 100);
    cout << "Minimum cut value: " << minCut << endl;
    
    return 0;
}