Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction:
2.
Approach:
3.
FAQs:
4.
Key Takeaways: 
Last Updated: Mar 27, 2024

Minimum Cut on a Graph Using a Maximum Flow Algorithm

Author Nishant Rana
0 upvote
Crack Google SDE interview : Essential projects
Speaker
Saurav Prateek
SDE-2 @
20 Jun, 2024 @ 01:30 PM

Introduction:

We are given a graph with N nodes. We need to find the minimum cut on the graph using the maximum flow algorithm.

Let us first discuss what is Minimum Cut in a graph:

The cut is a set of edges of a graph. If we remove these sets of edges from the graph, then that graph gets divided into two disjoint subsets.

An s-t cut is a cut that divides the source ‘s’ and the sink ‘t’ into different subsets. It will contain the edges going from the source’s side to the sink’s side. The capacity of the s-t cut is equal to the sum of the weight of each edge in the cut set.

 

 

In the above graph C1, C2, and C3 are the three different minimum cuts we can make. The weight of each of them is 14. Hence, we need to find the edges of one of the minimum cuts.

Approach:

The max-flow min-cut theorem states that in a flow network, the amount of maximum flow is equal to the capacity of the minimum cut. See here for proof of this theorem.

 

Let us first see a few concepts which we will use:-

  1. Residual Graph: Residual graph is a graph of a network flow that indicates if the additional flow is possible or not. If there is a path between the source node and the sink node in the residual graph, then that means the additional flow is possible. The weight of the edges of the residual graph indicates the residual capacity of that edge. The residual capacity of an edge is the original capacity minus the current flow.
  2. Ford Fulkerson algorithm: Ford-Fulkerson is a greedy algorithm that is useful to find the maximum flow of a network flow. It finds all the valid flow paths from the source node to the sink node until none is left and then adds them up. You can refer to this blog for more.

We will use the concept of the residual graph to print all the edges of the minimum cut set.

We follow these steps:-

1) We will run the Ford-Fulkerson algorithm and find the final residual graph.

2) We will then find those vertices that can be reached from the source in the residual graph.

3) The edges that point from a reachable vertex to a non-reachable vertex are part of minimum cut edges. In the end, we will print all such edges.

Refer to the below implementation of the above approach.

import java.util.*;
 
public class Graph {
  
    /*
      This function will return true if
      it find a path from source 's' to
      sink 't'. It will also fill the
      parent[] to store the path.
    */
    private static boolean bfs(int[][] residualGraph, int s, int t, int[] parent) {
        
        /*
          Creating a visited array
          to check if the current node
          is visited or not.
        */
        boolean[] visited = new boolean[residualGraph.length];
        
        /*
          Initializing a queue and adding
          source vertex to the queue and
          marking it visited.
        */
        Queue<Integer> q = new LinkedList<Integer>();
        q.add(s);
        visited[s] = true;
        parent[s] = -1;
        
        // Standard BFS Loop    
        while (!q.isEmpty()) {
            int v = q.poll();
            for (int i = 0; i < residualGraph.length; i++) {
                if (residualGraph[v][i] > 0 && !visited[i]) {
                    q.offer(i);
                    visited[i] = true;
                    parent[i] = v;
                }
            }
        }
          
        /*
          Return true if we reach the
          sink node starting from the
          source node.
        */
        return (visited[t] == true);
    }
    
    /*
      This function will help us
      to find all the reachable
      vertices from source. It will
      mark those nodes visited is we
      can reach that node from source.
    */
    private static void dfs(int[][] residualGraph, int s, boolean[] visited) {
        visited[s] = true;
        for (int i = 0; i < residualGraph.length; i++) {
                if (residualGraph[s][i] > 0 && !visited[i]) {
                    dfs(residualGraph, i, visited);
                }
        }
    }
 
    // This function will print the minimum s-t cut
    private static void minCut(int[][] graph, int s, int t) {
        int u,v;
        
        int[][] residualGraph = new int[graph.length][graph.length];
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph.length; j++) {
                residualGraph[i][j] = graph[i][j];
            }
        }
 
        // This array is filled by BFS and to store path
        int[] parent = new int[graph.length];
        
        // Augment the flow until there is path from source to sink    
        while (bfs(residualGraph, s, t, parent)) {
            
            /*
              Find minimum residual capacity of the edges
              along the path filled by BFS. Or we can say
              find the maximum flow through the path found.
            */
            int pathFlow = Integer.MAX_VALUE;        
            for (v = t; v != s; v = parent[v]) {
                u = parent[v];
                pathFlow = Math.min(pathFlow, residualGraph[u][v]);
            }
            
            for (v = t; v != s; v = parent[v]) {
                u = parent[v];
                residualGraph[u][v] = residualGraph[u][v] - pathFlow;
                residualGraph[v][u] = residualGraph[v][u] + pathFlow;
            }
        }
        
        // Flow is maximum now, find vertices reachable from s    
        boolean[] isVisited = new boolean[graph.length];    
        dfs(residualGraph, s, isVisited);
        
        /*
          Printing the edges that point
          from a reachable vertex to a
          non-reachable vertex in orginal graph.
        */
        for (int i = 0; i < graph.length; i++) {
            for (int j = 0; j < graph.length; j++) {
                if (graph[i][j] > 0 && isVisited[i] && !isVisited[j]) {
                    System.out.println(i + " - " + j);
                }
            }
        }
    }
}

 

Time Complexity: We are running a BFS on the Graph which takes O(E) time where E is the number of edges in the Residual Graph. For each edge, the flow in the worst case will reach its maximum value(let us say F). Hence, we will iterate the BFS algorithm F times. Hence, the overall time complexity is O(F * E).

 

Space Complexity: We are creating a Residual Graph, visited array, and maintaining a queue. All of them will contribute O(N) space complexity.

 

Get the tech career you deserve, faster!
Connect with our expert counsellors to understand how to hack your way to success
User rating 4.7/5
1:1 doubt support
95% placement record
Akash Pal
Senior Software Engineer
326% Hike After Job Bootcamp
Himanshu Gusain
Programmer Analyst
32 LPA After Job Bootcamp
After Job
Bootcamp

FAQs:

  1. What is the Cut Set?
    • The cut is a set of edges of a graph. If we remove these sets of edges from the graph, then that graph gets divided into two disjoint subsets.
  2. What is the Ford-Fulkerson algorithm?
    • The Ford-Fulkerson algorithm helps to find the maximum flow in the graph. The algorithm will begin with the empty flow, and at every step, it will find a path going from the source vertex to the sink vertex that generates more flow.

 

Key Takeaways: 

In this blog, we have covered the following things:

  1. We first discussed the approach to finding the Minimum Cut on a Graph Using a Maximum Flow Algorithm.
  2. Then we saw how to implement the approach discussed.

 

If you want to learn more about Graphs and want to practice some questions which require you to take your basic knowledge on Graphs a notch higher, then you can visit our Guided Path for Graphs

 

Until then, All the best for your future endeavors, and Keep Coding.








 

Live masterclass