In this program, we are going to share a C++ Program to Implement Max-Flow Min-Cut Theorem. If you are a beginner and want to start learning the C++ programming, then keep your close attention in this tutorial as I am going to share a program for C++ Program to Implement Max-Flow Min-Cut Theorem.
Copy the below C++ program and execute it with the help of GCC compiler. At the end of this program, We have shared the output of this program.
1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 17 18 19 20 21 22 23 24 25 26 27 28 29 30 31 32 33 34 35 36 37 38 39 40 41 42 43 44 45 46 47 48 49 50 51 52 53 54 55 56 57 58 59 60 61 62 63 64 65 66 67 68 69 70 71 72 73 74 75 76 77 78 79 80 81 82 83 84 85 86 87 88 89 90 91 92 93 94 95 | #include <iostream> #include <climits> #include <cstdlib> #include <cstring> #include <queue> #define V 6 using namespace std; int bfs(int rGraph[V][V], int s, int t, int parent[]) { bool visited[V]; memset(visited, 0, sizeof(visited)); queue <int> q; q.push(s); visited[s] = true; parent[s] = -1; while (!q.empty()) { int u = q.front(); q.pop(); for (int v = 0; v < V; v++) { if (visited[v] == false && rGraph[u][v] > 0) { q.push(v); parent[v] = u; visited[v] = true; } } } return (visited[t] == true); } void dfs(int rGraph[V][V], int s, bool visited[]) { visited[s] = true; for (int i = 0; i < V; i++) { if (rGraph[s][i] && !visited[i]) dfs(rGraph, i, visited); } } void minCut(int graph[V][V], int s, int t) { int u, v; int rGraph[V][V]; for (u = 0; u < V; u++) { for (v = 0; v < V; v++) rGraph[u][v] = graph[u][v]; } int parent[V]; while (bfs(rGraph, s, t, parent)) { int path_flow = 65536; for (v = t; v != s; v = parent[v]) { u = parent[v]; path_flow = 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; } } bool visited[V]; memset(visited, 0, sizeof(visited)); dfs(rGraph, s, visited); for (int i = 0; i < V; i++) { for (int j = 0; j < V; j++) { if (visited[i] && !visited[j] && graph[i][j]) cout << i << " - " << j << endl; } } return; } int main() { int graph[V][V] = { {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} }; minCut(graph, 0, 5); return 0; } |
1 – 3
4 – 3
4 – 5
