Code360 powered by Coding Ninjas X Naukri.com. Code360 powered by Coding Ninjas X Naukri.com
Table of contents
1.
Introduction💁
2.
Example📝
3.
Algorithm
4.
Code
5.
Complexities
6.
 Frequently Asked Questions
6.1.
What is a binary tree?
6.2.
What is time complexity in Data Structure?
6.3.
What is the purpose of finding the max value?
7.
Conclusion
Last Updated: Mar 27, 2024
Hard

Max Flow Problem

Introduction💁

The max flow problem is a very important problem that is used to find the maximum flow a network can carry. The max flow problem is often used to solve the problems associated with complex networks. A common problem that can be solved using the max flow problem is the circulation problem. The initial vertex in the max flow problem is known as the “source.” The final vertex is known as the “sink.” Each edge has a “limit.” The limit is the value that can be further carried by the vertice.

Introduction

Example📝

Let us consider a graph and understand what actually is the max flow problem. 

Graph

In the above example, the maximum flow that can be carried in the graph is 10.

In this example source is 0, and the sink is 5.

First Path: 0->2->3->5 (Min Capacity = 5)

Second Path: 0->2->4->5 (Min Capacity = 10)

Third Path: 0->1->2->4->5 (Min Capacity = 1)

Fourth Path: 0->1->2->3->5 (Min Capacity = 1)

So the maximum capacity out of the four paths is 10. Thus the maximum flow for the given graph is 10.

Algorithm

Number of Edges: (N)

Flow of Edge: F(n) (Capacity of each edge)

Capacity of Edge: C(n) (Current Capacity)

 

Step 1: Initialise the F(n) as 0 for each value of n, assign the max_value as 0

Step 2: Repeat the following steps for path P from s to t, where s is the source node, and t is the end node.

  •  The path exists if F(n) is less than or equal to C(n) for each value of n from s to t.
  • If the path is not valid, then return the max_value.
  • Else, we will find the minimum edge present in the path P,
    flow = min(C(n)-F(n)), max_flow += flow
    F(n) += flow 

Step 3: Return the max_value. 

Code

import java.util.*;


public class MaxFlowProblem {
    static int Vertice = 6;

  // Using binary first search for searching
  static boolean binaryFirstSearch(int Graph[][], int s, int t, int p[]) {
    boolean visited[] = new boolean[Vertice];
    for (int i = 0; i < Vertice; ++i)
      visited[i] = false;

    LinkedList<Integer> li = new LinkedList<Integer>();
    li.add(s);
    visited[s] = true;
    p[s] = -1;

    while (li.size() != 0) {
      int temp = li.poll();


      for (int i = 0; i < Vertice; i++) {
        if (visited[i] == false && Graph[temp][i] > 0) {
          li.add(i);
          p[i] = temp;
          visited[i] = true;
        }
      }
    }

    return (visited[t] == true);
  }

  //Find the maximum flow value
  static int findMaxFlow(int graph[][], int s, int t) {
    int u, v;
    int Graph[][] = new int[Vertice][Vertice];

    for (u = 0; u < Vertice; u++)
      for (v = 0; v < Vertice; v++)
        Graph[u][v] = graph[u][v];

    int p[] = new int[Vertice];

    int max_flow = 0;

    // # Updating the values for the edges
    while (binaryFirstSearch(Graph, s, t, p)) {
      int flow = Integer.MAX_VALUE;
      for (v = t; v != s; v = p[v]) {
        u = p[v];
        flow = Math.min(flow, Graph[u][v]);
      }


      for (v = t; v != s; v = p[v]) {
        u = p[v];
        Graph[u][v] -= flow;
        Graph[v][u] += flow;
      }

      // Adding the path flows
      max_flow += flow;
    }
    return max_flow;
  }

  public static void main(String[] args){
    int graph[][] = new int[][] { 
        { 0, 12, 14, 0, 0, 0 }, 
        { 0, 0, 1, 0, 0, 0 }, 
        { 0, 0, 0, 20, 10, 0 },
        { 0, 0, 0, 0, 0, 0 }, 
        { 0, 0, 0, 0, 0, 15 }, 
        { 0, 0, 0, 5, 0, 0 } };
    System.out.println("\n\nMaximum flow for the given graph is: " + findMaxFlow(graph, 0, 5) +"\n\n");

  }
}
You can also try this code with Online Java Compiler
Run Code
Ouptut

Complexities

The time complexity for the discussed algorithm is O(n^2), where n is the number of nodes. For each node, there will be n nodes to access. Thus the time complexity will be n^2. 

The space complexity for this algorithm is O(n^2), where n is the number of nodes. The system requires n^2 spaces to store the values present in the graph. For each node, there will be n nodes. Thus the space complexity will be n^2. 

 

Now let's discuss some frequently asked questions associated with the max flow problem.

FAQs

 Frequently Asked Questions

What is a binary tree?

A binary tree is a tree data structure in which each node has at most two children nodes. The children nodes are called the left node and the right node.

What is time complexity in Data Structure?

Time Complexity can be defined as the time required by a computer to perform an algorithm given the worst-case scenario for that algorithm.

What is the purpose of finding the max value?

The max flow problem is often used to solve the problems associated with complex networks. A common problem that can be solved using the max flow problem is the circulation problem.

Conclusion

This blog covered all the necessary points about finding the max flow problem. We further looked at an example to understand the implementation of the max flow problem in Java.

Do check out our blogs on object-oriented programming and Data Structures

Recommended Problems:

Don’t stop here. Check out Coding Ninjas for more unique courses and guided paths. Also, try Coding Ninjas Studio for more exciting articles, interview experiences, and fantastic Data Structures and Algorithms problems.

Live masterclass