Karger's algorithm for Minimum Cut | Set 1 (Introduction and Implementation) - GeeksforGeeks
Given an undirected and unweighted graph, find the smallest cut (smallest number of edges that disconnects the graph into two components).
The input graph may have parallel edges.
Below is simple Karger's Algorithm for this purpose. Below Karger's algorithm can be implemented in O(E) = O(V2) time.
We use disjoint-set(union-find) to detect whether the random picked edge belongs to same group.
http://www.programminggeek.in/2013/08/algorithm-to-find-minimum-cut-in-a-graph.html
https://en.wikipedia.org/wiki/Monte_Carlo_algorithm
A Monte Carlo algorithm is an algorithm for computers. It is used to simulate the behaviour of other systems. It is not an exact method, but a heuristical one. Usually it uses randomness and statistics to get a result. It is a computation process that uses random numbers to produce an outcome(s).
https://en.wikipedia.org/wiki/Las_Vegas_algorithm
a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. In other words, a Las Vegas algorithm does not gamble with the correctness of the result; it gambles only with the resources used for the computatio
Read full article from Karger's algorithm for Minimum Cut | Set 1 (Introduction and Implementation) - GeeksforGeeks
Given an undirected and unweighted graph, find the smallest cut (smallest number of edges that disconnects the graph into two components).
The input graph may have parallel edges.
Below is simple Karger's Algorithm for this purpose. Below Karger's algorithm can be implemented in O(E) = O(V2) time.
1) Initialize contracted graph CG as copy of original graph
2) While there are more than 2 vertices.
a) Pick a random edge (u, v) in the contracted graph.
b) Merge (or contract) u and v into a single vertex (update
the contracted graph).
c) Remove self-loops
3) Return cut represented by two vertices.
Karger’s algorithm is a Monte Carlo algorithm and cut produced by it may not be minimum.For example, the following diagram shows that a different order of picking random edges produces a min-cut of size 3.We use disjoint-set(union-find) to detect whether the random picked edge belongs to same group.
struct Graph{ // V-> Number of vertices, E-> Number of edges int V, E; // graph is represented as an array of edges. // Since the graph is undirected, the edge // from src to dest is also edge from dest // to src. Both are counted as 1 edge here. Edge* edge;};// A very basic implementation of Karger's randomized// algorithm for finding the minimum cut. Please note// that Karger's algorithm is a Monte Carlo Randomized algo// and the cut returned by the algorithm may not be// minimum alwaysint kargerMinCut(struct Graph* graph){ // Get data of given graph int V = graph->V, E = graph->E; Edge *edge = graph->edge; // Allocate memory for creating V subsets. struct subset *subsets = new subset[V]; // Create V subsets with single elements for (int v = 0; v < V; ++v) { subsets[v].parent = v; subsets[v].rank = 0; } // Initially there are V vertices in // contracted graph int vertices = V; // Keep contracting vertices until there are // 2 vertices. while (vertices > 2) { // Pick a random edge int i = rand() % E; // Find vertices (or sets) of two corners // of current edge int subset1 = find(subsets, edge[i].src); int subset2 = find(subsets, edge[i].dest); // If two corners belong to same subset, // then no point considering this edge if (subset1 == subset2) continue; // Else contract the edge (or combine the // corners of edge into one vertex) else { printf("Contracting edge %d-%d\n", edge[i].src, edge[i].dest); vertices--; Union(subsets, subset1, subset2); } } // Now we have two vertices (or subsets) left in // the contracted graph, so count the edges between // two components and return the count. int cutedges = 0; for (int i=0; i<E; i++) { int subset1 = find(subsets, edge[i].src); int subset2 = find(subsets, edge[i].dest); if (subset1 != subset2) cutedges++; } return cutedges;}int find(struct subset subsets[], int i){ // find root and make root as parent of i // (path compression) if (subsets[i].parent != i) subsets[i].parent = find(subsets, subsets[i].parent); return subsets[i].parent;}// A function that does union of two sets of x and y// (uses union by rank)void Union(struct subset subsets[], int x, int y){ int xroot = find(subsets, x); int yroot = find(subsets, y); // Attach smaller rank tree under root of high // rank tree (Union by Rank) if (subsets[xroot].rank < subsets[yroot].rank) subsets[xroot].parent = yroot; else if (subsets[xroot].rank > subsets[yroot].rank) subsets[yroot].parent = xroot; // If ranks are same, then make one as root and // increment its rank by one else { subsets[yroot].parent = xroot; subsets[xroot].rank++; }}https://en.wikipedia.org/wiki/Monte_Carlo_algorithm
A Monte Carlo algorithm is an algorithm for computers. It is used to simulate the behaviour of other systems. It is not an exact method, but a heuristical one. Usually it uses randomness and statistics to get a result. It is a computation process that uses random numbers to produce an outcome(s).
https://en.wikipedia.org/wiki/Las_Vegas_algorithm
a Las Vegas algorithm is a randomized algorithm that always gives correct results; that is, it always produces the correct result or it informs about the failure. In other words, a Las Vegas algorithm does not gamble with the correctness of the result; it gambles only with the resources used for the computatio
Read full article from Karger's algorithm for Minimum Cut | Set 1 (Introduction and Implementation) - GeeksforGeeks
