Max-Flow Min-Cut Theorem in C++

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.

```
/*
```

 * C++ Program to Implement 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;
```
```
}
```

$ 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.

If you wish to look at all C++ Programming examples, go to C++ Programs.

« Prev - C++ Program to Find Minimum Element in an Array using Binary Search

» Next - C++ Program to Perform String Matching using String Library

Related Posts:

Recommended Articles: