C++ Program to Implement Max-Flow Min-Cut Theorem

«
»
This C++ Program demonstrates implementation of Max-Flow_Min-Cut_Theorem.

Here is source code of the C++ Program to demonstrate Max-Flow_Min-Cut_Theorem. The C++ program is successfully compiled and run on a Linux system. The program output is also shown below.

  1. /*
  2.  * C++ Program to Implement Max-Flow Min-Cut Theorem
  3.  */
  4. #include <iostream>
  5. #include <climits>
  6. #include <cstdlib>
  7. #include <cstring>
  8. #include <queue>
  9. #define V 6
  10. using namespace std;
  11.  
  12. /*
  13.  * Returns true if there is a path from source 's' to sink 't' in
  14.  * residual graph. Also fills parent[] to store the path
  15.  */
  16. int bfs(int rGraph[V][V], int s, int t, int parent[])
  17. {
  18.     bool visited[V];
  19.     memset(visited, 0, sizeof(visited));
  20.     queue <int> q;
  21.     q.push(s);
  22.     visited[s] = true;
  23.     parent[s] = -1;
  24.     while (!q.empty())
  25.     {
  26.         int u = q.front();
  27.         q.pop();
  28.         for (int v = 0; v < V; v++)
  29.         {
  30.             if (visited[v] == false && rGraph[u][v] > 0)
  31.             {
  32.                 q.push(v);
  33.                 parent[v] = u;
  34.                 visited[v] = true;
  35.             }
  36.         }
  37.     }
  38.     return (visited[t] == true);
  39. }
  40.  
  41. /*
  42.  *  A DFS based function to find all reachable vertices from s.
  43.  */
  44. void dfs(int rGraph[V][V], int s, bool visited[])
  45. {
  46.     visited[s] = true;
  47.     for (int i = 0; i < V; i++)
  48.     {
  49.         if (rGraph[s][i] && !visited[i])
  50.            dfs(rGraph, i, visited);
  51.     }
  52. }
  53.  
  54. /*
  55.  * Prints the minimum s-t cut
  56.  */
  57. void minCut(int graph[V][V], int s, int t)
  58. {
  59.     int u, v;
  60.     int rGraph[V][V];
  61.     for (u = 0; u < V; u++)
  62.     {
  63.         for (v = 0; v < V; v++)
  64.              rGraph[u][v] = graph[u][v];
  65.     }
  66.     int parent[V];
  67.     while (bfs(rGraph, s, t, parent))
  68.     {
  69.         int path_flow = 65536;
  70.         for (v = t; v != s; v = parent[v])
  71.         {
  72.             u = parent[v];
  73.             path_flow = min(path_flow, rGraph[u][v]);
  74.         }
  75.         for (v = t; v != s; v = parent[v])
  76.         {
  77.             u = parent[v];
  78.             rGraph[u][v] -= path_flow;
  79.             rGraph[v][u] += path_flow;
  80.         }
  81.     }
  82.     bool visited[V];
  83.     memset(visited, 0, sizeof(visited));
  84.     dfs(rGraph, s, visited);
  85.     for (int i = 0; i < V; i++)
  86.     {
  87.         for (int j = 0; j < V; j++)
  88.         {
  89.             if (visited[i] && !visited[j] && graph[i][j])
  90.                 cout << i << " - " << j << endl;
  91.         }
  92.     }
  93.     return;
  94. }
  95. /*
  96.  * Main Contains Menu
  97.  */ 
  98.  
  99. int main()
  100. {
  101.     int graph[V][V] = { {0, 16, 13, 0, 0, 0},
  102.                         {0, 0, 10, 12, 0, 0},
  103.                         {0, 4, 0, 0, 14, 0},
  104.                         {0, 0, 9, 0, 0, 20},
  105.                         {0, 0, 0, 7, 0, 4},
  106.                         {0, 0, 0, 0, 0, 0}
  107.                       };
  108.  
  109.     minCut(graph, 0, 5);
  110.     return 0;
  111. }

$ g++ maxflow_mincut.cpp
$ a.out
1 - 3
4 - 3
4 - 5
 
 
------------------
(program exited with code: 0)
Press return to continue

Sanfoundry Global Education & Learning Series – 1000 C++ Programs.

Note: Join free Sanfoundry classes at Telegram or Youtube
advertisement
advertisement
If you wish to look at all C++ Programming examples, go to C++ Programs.

advertisement
advertisement
Subscribe to our Newsletters (Subject-wise). Participate in the Sanfoundry Certification contest to get free Certificate of Merit. Join our social networks below and stay updated with latest contests, videos, internships and jobs!

Youtube | Telegram | LinkedIn | Instagram | Facebook | Twitter | Pinterest
Manish Bhojasia - Founder & CTO at Sanfoundry
Manish Bhojasia, a technology veteran with 20+ years @ Cisco & Wipro, is Founder and CTO at Sanfoundry. He lives in Bangalore, and focuses on development of Linux Kernel, SAN Technologies, Advanced C, Data Structures & Alogrithms. Stay connected with him at LinkedIn.

Subscribe to his free Masterclasses at Youtube & technical discussions at Telegram SanfoundryClasses.