Programming Geek
Rated 4.7/5 based on 1446 reviews

Algorithm to Find Minimum Cut in a Graph

A cut in a graph is a set C=(S,T) of nodes such that S and T are two disjoint subsets of all nodes of the graph. The size of the cut is the number of edges between two disjoint subsets. A cut is said to be minimum if the size of the cut is not larger than size of any other cut of the graph.

A graph with two cuts. The dotted line in red is a cut with three crossing edges. The dashed line in green is the min-cut of this graph, crossing only two edges.(src:wikipedia)


 To find the minimum cut of a graph, we can use Karger algorithm as illustrated below :

Algorithm : 

1)While there are more than two vertices repeat step 2 to 4.

2) Select a random edge of the graph.

3)Merge the two vertices of the edge.

4)Remove self loops.

5) Return the cut represented by two vertices.

Although this algorithm can not guarantee the success in a single run but multiple run of the algorithm can award you a minimum cut.

A newbie generally faces problem while attempting to merge the vertices. Here i give you the main part of my implementation in JAVA .



void kargerCut(int v1, int v2) //v1 and v2 are random vertices passed to this method
{               //list contains list of the vertices
  ArrayList<Integer> first = list.get(v1);//list of vertices from v1th list 
  ArrayList<Integer> second = list.get(v2);//list of vertices from v2th list
  int num1=first.get(0);//get first number from first list
  int num2=second.get(0);//get second number from second list
  first.addAll(second);//add all vertices of second list to first list
  list.set(v1, first);//update the list

  for (int i = 0; i < list.size(); i++) {//This loop replaces the num2 by num1 in the entire list
   ArrayList<Integer> temp = list.get(i);
   for (int j = 1; j < temp.size(); j++) {

    if ( temp.get(j) == num2 ) {
     temp.set(j, num1 );
    }

    
   }
  }

                //remove self loops in the first list
  for (int i = 1; i < first.size(); i++) {
   if (first.get(i) == num1 ) {
    first.remove(i);
    i--;
   }
  }

  list.remove(v2);//removes v2th list

}



No comments :

Post a Comment