Do you think IIT Guwahati certified course can help you in your career?
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.
Example📝
Let us consider a graph and understand what actually is the max flow problem.
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
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.
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.
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.
34+ registered 
