Hi guys, I'm now experimenting with FordFulkerson Algorithm, which I am using to print the mincut (as in, edges which comprise the mincut). However, I am having some issues with memory and I wanted to translate this code to use only adjacency lists representation, instead of adjacency matrix... If someone could help me I'd be really glad, as I've spent over 72 hours with this problem... :/
Note: my main issue seems to be how can I use C++ iterators to "pass" the adjacency list to both DFS and BFS in order not to get lots of segfaults... As I've rarely used adjacency lists and as my iterator knowledge is poor, I'd like some guidance :D Best, Bruno asked 31 Mar '14, 23:11

Here is a bfs implemented using adjacency list: http://ideone.com/amqg4O Basically in adjacency list you store only vertices adjacent to a given vertex. This saves up on space. In the above code, vector < vector < int > >g is an adjacency list where g[i] stores vertices adjacent to the i'th vertex. To iterate over the list of adjacent vertices of the i'th vertex you can just use the following loop: for(int i = 0 ; i < g[i].size() ; i++) { /do necessary stuff/ }. As for passing the adjacency list to a function, you can do that in exactly the same way as you pass the adjacency matrix in your code. No segfaults will occur. If you need more clarifications, feel free to comment :) Regards answered 31 Mar '14, 23:25

Hi, Thanks for your help in the first place :) However, I don't think I can do it that way, mostly because I need to "entwine" the DFS and the BFS together, as you might see here:
The main issues I have are three: 1) I only want to print the edges which will be "crossed" by the mincut; 2) I need to have both a DFS and BFS running "synced" and both with the same graph structure; 3) I can't seem to figure out a way of doing the double for loop in the end when I do not have a square matrix. Obviously if Graph[i][j] is 0 in an Adjacency Matrix representation, it might not even exist in an Adjacency List one... Also, last but not least, my graph needs to be weighted (I'm giving a specfic weight to the edges, say 1); For that I use a vector<vector<pii> > Graph; where an edge is denoted as Graph[i]  Graph[i][j].first ... Something like this:
How would I use this structure in the above code? answered 01 Apr '14, 01:57

Thanks! But, maybe I didnt make myself too clear, I know how to convert between both representations, in fact, the weighted adjacency list idea is given above... My issue seems to be with how that representation will interfere with the general algorithm of FordFulkerson, as I can't print the edges in a direct adjacency list representation... For the example graph in the code as comment, the output should be:
I cant manage to reproduce it with the adjacency list representation... :( answered 01 Apr '14, 04:53

Printing is the required ans is trivial. It can be done using the following code (graph[i] is the adjacency list of i'th vertex):
answered 01 Apr '14, 16:16
