C++ Programming Code Examples C++ > Computer Graphics Code Examples Program to Implement Network_Flow Problem Program to Implement Network_Flow Problem This C++ Program demonstrates implementation of Network_Flow Problem. #include <iostream> #include <climits> #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 */ bool 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); } /* Returns tne maximum flow from s to t in the given graph */ int fordFulkerson(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]; int max_flow = 0; while (bfs(rGraph, s, t, parent)) { int path_flow = INT_MAX; 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; } max_flow += path_flow; } return max_flow; } /* 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} }; cout << "The maximum possible flow is " << fordFulkerson(graph, 0, 5); return 0; }