Day 20 · Week 4

Network Flow & Full-Course Review

Level 6 · Advanced + Capstone · 2 hrs: ~40 min flow · ~80 min review

🧠 Mental Model — Max Flow

Picture a network of pipes with capacities from a source to a sink. Maximum flow is the greatest rate you can push through. The recurring trick: repeatedly find an augmenting path with spare capacity and push flow along it, using residual edges that let you "undo" earlier choices.

Network flow is rare in standard interviews but appears at senior levels or when a problem secretly reduces to matching/assignment. Aim for awareness: recognize the reduction, know Edmonds-Karp exists.

⚙️ Ford-Fulkerson / Edmonds-Karp

While an augmenting path from source to sink exists in the residual graph:
Find one (Edmonds-Karp uses BFS → shortest augmenting path).
Push flow = the path's minimum residual capacity (the bottleneck).
Update residuals: subtract on forward edges, add on reverse edges.

Max-Flow Min-Cut Theorem (Ford & Fulkerson, 1956) The maximum flow from source to sink equals the minimum total capacity of any cut separating them.

Intuition Any flow is bounded by every cut's capacity (all flow crosses it). At termination no augmenting path remains, so the set of source-reachable residual vertices defines a cut whose capacity exactly equals the flow — matching the lower bound. Hence flow = min cut. ∎

Algorithm	Time	Note
Ford-Fulkerson (DFS)	O(E · maxflow)	Only integral capacities; can be slow
Edmonds-Karp (BFS)	O(V · E²)	Shortest augmenting path; standard to cite
Dinic's	O(V² · E)	Level graph + blocking flow; fast in practice

💻 Reference Implementation (Java)

Edmonds-Karp skeleton (BFS augmenting paths on a capacity matrix).

import java.util.*;

/** Edmonds-Karp max flow. cap[u][v] = capacity. Returns max flow s→t. */
public int maxFlow(int[][] cap, int s, int t, int n) {
    int flow = 0;
    while (true) {
        int[] parent = new int[n];
        Arrays.fill(parent, -1);
        parent[s] = s;
        Queue<Integer> q = new ArrayDeque<>();
        q.offer(s);
        while (!q.isEmpty() && parent[t] == -1) {   // BFS for augmenting path
            int u = q.poll();
            for (int v = 0; v < n; v++)
                if (parent[v] == -1 && cap[u][v] > 0) {
                    parent[v] = u;
                    q.offer(v);
                }
        }
        if (parent[t] == -1) break;          // no path ⇒ done

        int bottleneck = Integer.MAX_VALUE;      // min residual on path
        for (int v = t; v != s; v = parent[v])
            bottleneck = Math.min(bottleneck, cap[parent[v]][v]);
        for (int v = t; v != s; v = parent[v]) {   // update residuals
            cap[parent[v]][v] -= bottleneck;
            cap[v][parent[v]] += bottleneck;           // reverse edge
        }
        flow += bottleneck;
    }
    return flow;
}

🎭 Problem Variances — when a problem is secretly max-flow

Disguise / phrasing	Reduces to	Twist to handle
"Maximum bipartite matching"	Max flow (unit capacities)	Source→left→right→sink, cap 1
"Max # of edge/vertex-disjoint paths"	Max flow (Menger)	Unit caps; split vertices for vertex-disjoint
"Min cut to separate / sabotage network"	Min cut = max flow	Compute max flow, read the cut
"Assign tasks/workers with limits"	Flow with capacities	Capacities encode the limits
"Project selection / max profit with prereqs"	Min-cut (closure)	Classic max-flow reduction
"Escape the grid (multiple exits, no overlap)"	Vertex-capacity flow	Split each cell into in/out with cap 1

Interview reality: you rarely code Dinic's live. The valuable skill is spotting the reduction ("this is bipartite matching → max flow") and stating min-cut = max-flow.

🗺️ Full-Course Master Recognition Table

The capstone cheat-sheet — map any graph problem to its algorithm in seconds.

Signal	Algorithm	Day
Fewest steps, unweighted	BFS	2
Reachability, enumerate paths, region shape	DFS	3
Count groups (undirected)	Connected components	4
Shortest path, non-negative weights	Dijkstra	7
Negative edges / bounded hops	Bellman-Ford	6
All-pairs shortest, small V	Floyd-Warshall	7
Weights ∈ {0,1}	0-1 BFS	6
Dynamic connectivity / merging groups	Union-Find	8–10
Dependency ordering (DAG)	Topological sort	11–12
Directed cycle detection	3-color DFS / Kahn count	12
Connect all at min cost	MST (Kruskal / Prim)	13–14
Two-group split / conflicts apart	Bipartite check	16
Directed mutual reachability / 2-SAT	Tarjan's SCC	17
Single points of failure (undirected)	Bridges / articulation	18
Goal-directed search / heuristic	A*	19
Use every edge once / itinerary	Eulerian (Hierholzer)	19
Matching / min cut / capacity limits	Max flow	20

🎯 Capstone Review (~80 min)

Mock (45 min): pick one random Med + one Hard from any week; solve under time, verbalizing aloud.
Weakness pass: revisit the 2–3 problems you struggled with most across the course.
Recall sprint: from memory, write skeletons for BFS, DFS, Dijkstra, Union-Find, topo sort, and one MST. If any stalls, that's your next study target.

You've covered all 6 levels. The differentiator now isn't knowing more algorithms — it's recognizing which one a disguised problem needs and coding it cleanly under pressure. Drill the recognition table until it's reflexive.

📚 References

Ford & Fulkerson (1956) — "Maximal flow through a network," Canadian J. Math. 8. Max-flow min-cut.
Edmonds & Karp (1972) — "Theoretical improvements in algorithmic efficiency for network flow problems," JACM 19(2).
Dinic (1970) — the blocking-flow algorithm.
CLRS, 3rd ed., Ch. 26 — Maximum flow, bipartite matching reduction.

← Day 19: A* + Eulerian Index →