Senior LevelData Structures & Algorithms
How does Ford-Fulkerson compute Maximum Flow in a network?
❓ Interview Prompt: Explain Max-Flow, Ford-Fulkerson augmenting paths, residual graph, Edmonds-Karp O(VE²), and the Max-Flow Min-Cut theorem.
Maximum Flow finds the maximum amount of "flow" from source $s$ to sink $t$ in a directed capacity graph.
Ford-Fulkerson Method:
1
Initialise all flows to 0.
2
While there exists an augmenting path (source → sink with residual capacity) in the residual graph:
•
Find the bottleneck capacity $c$ of the path.
•
Add $c$ to flow along forward edges; subtract $c$ from backward (reverse) edges.
3
When no augmenting path exists → maximum flow found.
Edmonds-Karp: $O(VE^2)$
Uses BFS (shortest path by hops) to find augmenting paths, giving polynomial time guarantee.
Max-Flow Min-Cut Theorem:
Max flow = weight of minimum cut separating source from sink.
Code Implementation Example
typescript
// Edmonds-Karp (BFS-based Ford-Fulkerson) — O(VE^2)
function maxFlow(graph: number[][], source: number, sink: number): number {
const n = graph.length;
let totalFlow = 0;
while (true) {
// BFS to find augmenting path
const parent = new Array(n).fill(-1);
parent[source] = source;
const queue = [source];
while (queue.length && parent[sink] === -1) {
const u = queue.shift()!;
for (let v = 0; v < n; v++) {
if (parent[v] === -1 && graph[u][v] > 0) {
parent[v] = u;
queue.push(v);
}
}
}
if (parent[sink] === -1) break; // no augmenting path
// Find bottleneck capacity
let flow = Infinity;
for (let v = sink; v !== source; v = parent[v])
flow = Math.min(flow, graph[parent[v]][v]);
// Update residual capacities
for (let v = sink; v !== source; v = parent[v]) {
graph[parent[v]][v] -= flow;
graph[v][parent[v]] += flow;
}
totalFlow += flow;
}
return totalFlow;
}💡Edmonds-Karp max flow with BFS augmenting paths — O(VE²).
🎯 Interview Key Takeaway
Max-Flow = Min-Cut (fundamental theorem). Edmonds-Karp gives O(VE²). Applications: bipartite matching, network reliability, airline scheduling.
#DSA#Max Flow#Ford-Fulkerson#Graph#Senior
Back to all Data Structures & Algorithms Questions→