A bipartite graph with a source and sink is given as shown below. The capacity of every edge is 1 unit : Source : GeeksforGeeks
I'm trying to find the maximum flow from source to sink. One approach would be using the Ford-Fulkerson Algorithm for Maximum Flow Problem, which is applicable to all the graphs. I found a simple approach to find the maximum flow(too simple to be correct!) and I'm not able to find any error in the approach.
Approach :
c1 = Count the number of vertices having non zero number of edges originating from it ,in the list of vertices having outgoing edges.
c2 = Count the number of vertices having non zero number of edges converging into it ,in the list of vertices having incoming edges.
The max flow would be the minimum of both these numbers,i.e., min(c1,c2).[Since any path needs one vertex from the outgoing vertices list, and other from incoming vertices list.]
Any help would be appreciated.
Consider a graph like
*--*
/
/
* *
/
/
*--*
(The patch of working by connected component doesn't fix things; connect the lower left to the upper right.)