Ford | Java program for implementation of Ford Fulkerson algorithm ; Number of vertices in graph ; Returns true if there is a path from source ' s ' to sink ' t ' in residual graph . Also fills parent [ ] to store the path ; Create a visited array and mark all vertices as not visited ; Create a queue , enqueue source vertex and mark source vertex as visited ; Standard BFS Loop ; If we find a connection to the sink node , then there is no point in BFS anymore We just have to set its parent and can return true ; We didn 't reach sink in BFS starting from source,  so return false ; Returns tne maximum flow from s to t in the given graph ; Create a residual graph and fill the residual graph with given capacities in the original graph as residual capacities in residual graph Residual graph where rGraph [ i ] [ j ] indicates residual capacity of edge from i to j ( if there is an edge . If rGraph [ i ] [ j ] is 0 , then there is not ) ; This array is filled by BFS and to store path ; There is no flow initially ; Augment the flow while tere is path from source to sink ; Find minimum residual capacity of the edhes along the path filled by BFS . Or we can say find the maximum flow through the path found . ; update residual capacities of the edges and reverse edges along the path ; Add path flow to overall flow ; Return the overall flow ; Driver program to test above functions ; Let us create a graph shown in the above example
import java . io . * ; import java . lang . * ; import java . util . * ; import java . util . LinkedList ; class MaxFlow { static final int V = 6 ; boolean bfs ( int rGraph [ ] [ ] , int s , int t , int parent [ ] ) { boolean visited [ ] = new boolean [ V ] ; for ( int i = 0 ; i < V ; ++ i ) visited [ i ] = false ; LinkedList < Integer > queue = new LinkedList < Integer > ( ) ; queue . add ( s ) ; visited [ s ] = true ; parent [ s ] = - 1 ; while ( queue . size ( ) != 0 ) { int u = queue . poll ( ) ; for ( int v = 0 ; v < V ; v ++ ) { if ( visited [ v ] == false && rGraph [ u ] [ v ] > 0 ) { if ( v == t ) { parent [ v ] = u ; return true ; } queue . add ( v ) ; parent [ v ] = u ; visited [ v ] = true ; } } } return false ; } int fordFulkerson ( int graph [ ] [ ] , int s , int t ) { int u , v ; int rGraph [ ] [ ] = new int [ V ] [ V ] ; for ( u = 0 ; u < V ; u ++ ) for ( v = 0 ; v < V ; v ++ ) rGraph [ u ] [ v ] = graph [ u ] [ v ] ; int parent [ ] = new int [ V ] ; int max_flow = 0 ; while ( bfs ( rGraph , s , t , parent ) ) { int path_flow = Integer . MAX_VALUE ; for ( v = t ; v != s ; v = parent [ v ] ) { u = parent [ v ] ; path_flow = Math . min ( path_flow , rGraph [ u ] [ v ] ) ; } for ( v = t ; v != s ; v = parent [ v ] ) { u = parent [ v ] ; rGraph [ u ] [ v ] -= path_flow ; rGraph [ v ] [ u ] += path_flow ; } max_flow += path_flow ; } return max_flow ; } public static void main ( String [ ] args ) throws java . lang . Exception { int graph [ ] [ ] = new int [ ] [ ] { { 0 , 16 , 13 , 0 , 0 , 0 } , { 0 , 0 , 10 , 12 , 0 , 0 } , { 0 , 4 , 0 , 0 , 14 , 0 } , { 0 , 0 , 9 , 0 , 0 , 20 } , { 0 , 0 , 0 , 7 , 0 , 4 } , { 0 , 0 , 0 , 0 , 0 , 0 } } ; MaxFlow m = new MaxFlow ( ) ; System . out . println ( " The ▁ maximum ▁ possible ▁ flow ▁ is ▁ " + m . fordFulkerson ( graph , 0 , 5 ) ) ; } }