DSA Maximum Flow

DSA – Maximum Flow (Complete Beginner Guide)
(Concept • Terminology • Ford–Fulkerson • Edmonds–Karp • Example • Code • Complexity • Interview Tips)

Maximum Flow is a classic graph problem where we find the maximum possible flow from a source to a sink without violating capacity constraints.

One-line idea:
Push as much flow as possible from Source (S) to Sink (T).

1️⃣ What is the Maximum Flow Problem?

Given

A directed graph
Each edge has a capacity
A source (S) and a sink (T)

Find

The maximum flow from S to T
Such that:
- Flow on edge ≤ capacity
- Flow conservation holds at intermediate vertices

2️⃣ Key Terminology

Term	Meaning
Flow	Amount sent through an edge
Capacity	Max flow an edge can carry
Residual Capacity	Remaining capacity
Augmenting Path	Path with available capacity
Residual Graph	Graph showing remaining capacities

3️⃣ Real-Life Applications

✔ Network bandwidth optimization
✔ Traffic / water / pipeline systems
✔ Bipartite matching
✔ Image segmentation
✔ Project scheduling

4️⃣ Flow Network Example

5️⃣ Core Idea (Augmenting Path)

Find a path from S → T
Minimum capacity on that path = bottleneck
Push that flow
Update residual graph
Repeat until no path exists

6️⃣ Ford–Fulkerson Algorithm

Idea

Repeatedly find any augmenting path
Add flow until no path exists

Path search can be DFS or BFS

Complexity

7️⃣ Edmonds–Karp Algorithm

Improved Ford–Fulkerson

Difference

Uses BFS to find shortest augmenting path
Guarantees polynomial time

Complexity

Most commonly asked in interviews

8️⃣ Step-by-Step Flow (Edmonds–Karp)

Initialize all flows = 0
Run BFS on residual graph to find S → T
Find bottleneck capacity
Augment flow
Update residual capacities
Repeat until BFS fails

9️⃣ Edmonds–Karp C++ Implementation

#include <bits/stdc++.h>
using namespace std;

#define V 6

bool bfs(int rGraph[V][V], int s, int t, int parent[]) {
    bool visited[V];
    memset(visited, false, 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] && rGraph[u][v] > 0) {
                parent[v] = u;
                visited[v] = true;
                if(v == t) return true;
                q.push(v);
            }
        }
    }
    return false;
}

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 maxFlow = 0;

    while(bfs(rGraph, s, t, parent)) {
        int pathFlow = INT_MAX;

        for(v = t; v != s; v = parent[v]) {
            u = parent[v];
            pathFlow = min(pathFlow, rGraph[u][v]);
        }

        for(v = t; v != s; v = parent[v]) {
            u = parent[v];
            rGraph[u][v] -= pathFlow;
            rGraph[v][u] += pathFlow;
        }

        maxFlow += pathFlow;
    }

    return maxFlow;
}

#include <bits/stdc++.h>

using namespace std;

#define V 6

bool bfs(int rGraph[V][V], int s, int t, int parent[]) {

bool visited[V];

memset(visited, false, 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] && rGraph[u][v] > 0) {

parent[v] = u;

visited[v] = true;

if(v == t) return true;

q.push(v);

}

return false;

}

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 maxFlow = 0;

while(bfs(rGraph, s, t, parent)) {

int pathFlow = INT_MAX;

for(v = t; v != s; v = parent[v]) {

u = parent[v];

pathFlow = min(pathFlow, rGraph[u][v]);

}

for(v = t; v != s; v = parent[v]) {

u = parent[v];

rGraph[u][v] -= pathFlow;

rGraph[v][u] += pathFlow;

}

maxFlow += pathFlow;

}

return maxFlow;

}

🔟 Time & Space Complexity

Algorithm	Time Complexity
Ford–Fulkerson	O(E × MaxFlow)
Edmonds–Karp	O(V × E²)

Space: O(V²) (adjacency matrix)

1️⃣1️⃣ Maximum Flow vs Minimum Cut

Max-Flow Min-Cut Theorem

Maximum flow value = Minimum cut capacity
If you find max flow → you also found min cut

1️⃣2️⃣ Common Interview Questions

Q1. Why residual graph is needed?
👉 To track remaining capacity and reverse flow

Q2. Difference between Ford–Fulkerson & Edmonds–Karp?
👉 Path selection (DFS vs BFS)

Q3. Can edges have negative capacity?
👉 No

Q4. Is Maximum Flow applicable to undirected graphs?
👉 Convert edges to bidirectional directed edges

Final Summary

✔ Works on directed graphs
✔ Uses augmenting paths
✔ Residual graph is key
✔ Edmonds–Karp is interview-friendly
✔ Foundation for matching & min-cut problems

DSA Maximum Flow

1️⃣ What is the Maximum Flow Problem?

2️⃣ Key Terminology

3️⃣ Real-Life Applications

4️⃣ Flow Network Example

5️⃣ Core Idea (Augmenting Path)

6️⃣ Ford–Fulkerson Algorithm

Idea

Complexity

7️⃣ Edmonds–Karp Algorithm

Difference

Complexity

8️⃣ Step-by-Step Flow (Edmonds–Karp)

9️⃣ Edmonds–Karp C++ Implementation

🔟 Time & Space Complexity

1️⃣1️⃣ Maximum Flow vs Minimum Cut

1️⃣2️⃣ Common Interview Questions

Final Summary

DSA Tutorial

Arrays

Linked Lists

Stacks & Queues

Hash Tables

Trees

Graphs

Shortest Path