Hello!! I have recently studied max flow algorithm and about bipartite matching.As bipartite graph is simpler compared to general graph,is there any way we could reduce the space and time complexity when we apply edmonds_karp to it?
Can we reduce the space complexity to O(N) instead of using usual adjacency matrix for residual graph representation which takes up O(N^2)?
Switch to an adjacency list representation for the residual graph. Now since we need to find some augmenting path and also update the flows on the augmenting path, it will be more convenient to store edge indices instead of (to_vertex, capactity, cur_flow) in the adjacency list. This way we can access the next vertex corresponding to the edge as well as the edge itself so we can easily manipulate the edge values (specifically the flow value of the edge). Now the edges can be stored separately in some vector/array. Each edge is described by four parameters, the first two being its endpoints (to, from), then the next two values will be the edge capacity and the current flow across the edge. Now with some minor modifications to your max flow algorithm according to what I've said, you will have achieved space complexity linear in size of the graph (O(N + M)).
Note that this space optimization can be done regardless of whether the graph is bipartite or not, that is, for a general graph.
Also note that we do not need to explicitly construct a flow graph and find max flow of the graph when we want to find bipartite matching (link).
where did you even find a code using adjacency matrix for residual graph? sounds really terrible...
Most of the websites i went through(emaxx,gfg,etc) has adj matrix representations for residual graph..
Do not use gfg to study, their codes have too many errors / messy.
I've clicked two articles related to bipartite matching in e-maxx/ru (with translator) and both code had adjacency list, so not sure which article are you referring to.