C++ Programming Code Examples C++ > Computer Graphics Code Examples Program to Implement Max-Flow_Min-Cut_Theorem Program to Implement Max-Flow_Min-Cut_Theorem This C++ Program demonstrates implementation of Max-Flow_Min-Cut_Theorem. #include <iostream> #include <climits> #include <cstdlib> #include <cstring> #include <queue> #define V 6 using namespace std; /* Returns true if there is a path from source 's' to sink 't' in residual graph. Also fills parent[] to store the path */ 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); } /* A DFS based function to find all reachable vertices from s. */ 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); } } /* Prints the minimum s-t cut */ 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; } /* Main Contains Menu */ 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; }
