Skip to content
Tutorials Center
My learning

Topics

Lesson 145 of 225 ยท Shortest Paths and Spanning Trees

Maximum Flow and Matching

Learn network flow in Python: residual graphs, Ford-Fulkerson, Edmonds-Karp, the max-flow min-cut theorem and how to solve bipartite matching with flow.

Imagine a city's water system. A pumping station (the source) pushes water through pipes of different widths toward a reservoir (the sink). Each pipe can carry only so much per minute. How much water can reach the reservoir in total? That question is the maximum flow problem, and it hides inside many other problems: shipping goods through a road network, routing data packets, scheduling jobs to machines, or pairing students with projects.

The beautiful part is that one algorithm solves all of them. You model the situation as a directed graph with capacities, run a max-flow algorithm, and read off the answer. This lesson builds the standard algorithms from scratch, proves why they stop at the right answer (the max-flow min-cut theorem), and then uses flow to solve bipartite matching. It builds on BFS and graph representations.

Flow networks

A flow network is a directed graph where every edge u -> v has a capacity c(u, v) >= 0, plus two special vertices: a source s and a sink t. A flow assigns each edge a value f(u, v) such that:

  1. Capacity constraint: 0 <= f(u, v) <= c(u, v). A pipe cannot carry more than its capacity.
  2. Flow conservation: for every vertex except s and t, the flow in equals the flow out. Water does not appear or vanish at junctions.

The value of a flow is the total leaving the source (which equals the total arriving at the sink). We want the largest possible value.

TEXT
  S --10--> A --4----------> C --10--> T
  |         |                ^
  |         +--8--> D --6----+
  |         |       ^  |
  |         2       |  +--10--> T
  |         v       9
  +--10---> B ------+

(both T's are the same vertex; A -> B has capacity 2)

A first idea is greedy: find any path from S to T, push as much as fits, repeat. The trouble is that an early choice can block a better overall plan. The fix is a clever bookkeeping structure that lets the algorithm undo earlier decisions.

The residual graph

For each edge u -> v with capacity c and current flow f, the residual graph has:

  • a forward edge u -> v with residual capacity c - f (how much more we can push), and
  • a backward edge v -> u with residual capacity f (how much we can cancel).

Pushing flow backward along v -> u means "send less through u -> v", which frees capacity to be used on another route. An augmenting path is any path from s to t in the residual graph. Its bottleneck is the smallest residual capacity on the path, and we can push exactly that much more flow.

TEXT
before:   u --(cap 5, flow 0)--> v      residual: u->v: 5     v->u: 0
push 3:   u --(cap 5, flow 3)--> v      residual: u->v: 2     v->u: 3
undo 1:   u --(cap 5, flow 2)--> v      residual: u->v: 3     v->u: 2

This is the key trick. Storing only residual capacities (one number per directed edge, including the reverse edges that start at 0) is enough: pushing x along u -> v does cap[u][v] -= x and cap[v][u] += x.

Ford-Fulkerson and Edmonds-Karp

The Ford-Fulkerson method is a simple loop:

  1. Start with zero flow.
  2. While the residual graph has an augmenting path from s to t: push the bottleneck amount along it.
  3. When no augmenting path exists, the flow is maximum.

The method does not say how to find the path. If you use DFS and capacities are huge numbers, the running time can depend on the capacities themselves, not just the graph size. Edmonds-Karp fixes this by always choosing the augmenting path with the fewest edges, which is just a BFS. It then runs in O(V * E^2) time regardless of capacities, because each augmentation saturates at least one edge on a shortest path, and shortest-path lengths never decrease.

Python Edmonds-Karp max flow

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Read the output as a story. Each line is one augmenting path, found by BFS, with the amount pushed. When BFS can no longer reach T in the residual graph, the loop ends and the sum of the pushed amounts is the maximum flow.

Tracing a tiny example

Take a diamond where the greedy choice is a trap:

TEXT
   S ---1---> A ---1---> T
   |          |           ^
   |          1           |
   |          v           |
   +---1----> B ----1-----+

all capacities are 1: S->A, S->B, A->B, A->T, B->T

If we first push 1 along S -> A -> B -> T, both S->A and B->T are full. The remaining routes look blocked, yet the true maximum is 2 (S->A->T and S->B->T). The residual graph rescues us: after the first push there is a backward edge B -> A with residual 1. The path S -> B -> A -> T uses it, cancelling the A -> B flow, and the total becomes 2. The algorithm never needs to "guess" correctly because mistakes can always be undone.

Python Undoing a bad first choice

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Max-flow min-cut

A cut splits the vertices into two groups: a set X containing s and the rest containing t. The capacity of the cut is the sum of capacities of edges going from X to the other side. Any flow must cross every cut, so the flow value can never exceed the capacity of any cut. In particular, the maximum flow is at most the minimum cut.

The remarkable theorem is that they are equal:

max flow = min cut

Why? When Ford-Fulkerson stops, no augmenting path exists. Let X be all vertices still reachable from s in the residual graph. Every edge from X to outside must be saturated (otherwise its endpoint would be reachable), and every edge coming back into X must carry zero flow. So the flow across this cut equals the cut's capacity, and since no flow can beat any cut, the flow is maximum and the cut is minimum.

This gives us a free byproduct: after the algorithm, run one more search from the source in the residual graph. The reachable set is one side of a minimum cut, and the saturated edges leaving it are the bottleneck edges of the network.

Python Finding the minimum cut

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

The cut capacity matches the flow value exactly. That is a certificate: anyone can verify in linear time that the answer is optimal without trusting the algorithm.

Bipartite matching with flow

In a bipartite graph the vertices split into a left group and a right group, and edges only connect left to right. A matching is a set of edges that share no vertex. A maximum matching has as many edges as possible. Think of students (left), projects (right), and an edge when a student is willing to do a project: we want as many students as possible to get their own project.

Flow solves this with a clean construction:

  1. Add a new source s with an edge of capacity 1 to every left vertex.
  2. Keep each original edge left to right with capacity 1.
  3. Add an edge of capacity 1 from every right vertex to a new sink t.

An integer flow of value k corresponds to a matching with k edges: the capacity-1 edges next to s and t make sure each vertex is used at most once.

TEXT
         s
      /  |  \          every s->left and right->t edge has capacity 1
     L1  L2  L3        every L->R edge has capacity 1
     |\ /|   |
     | X |   |         max flow = size of the largest matching
     R1  R2  R3
      \  |  /
         t
Python Matching students to projects

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Four students and four projects, and all four get a project. Ben only likes Robot and Dev only likes Website, so Ana and Cleo have to settle for something else. A greedy "first free project" strategy could give Ana the Robot and strand Ben; the backward edges in the residual graph let the flow reroute Ana automatically.

A leaner specialist: Kuhn's algorithm

For matching alone you can skip building the network. Kuhn's algorithm tries to find an augmenting path for each left vertex using DFS, "stealing" a right vertex from its current partner if that partner can move elsewhere. It is exactly Ford-Fulkerson specialised to unit capacities, running in O(V * E).

Python Kuhn's matching algorithm

Press Run (or Ctrl + Enter) to see the result here.

Program input ยท what you'd type while the program runs

Type the answers before you press Run, one per line. Each time the program reads a line (with input()), it gets the next line from this box.

Complexity

Algorithm Time Notes
Ford-Fulkerson (DFS) O(E * F) F is the max flow value; only good for small integer capacities
Edmonds-Karp (BFS) O(V * E^2) independent of capacities
Dinic's algorithm O(V^2 * E) blocking flows on a BFS level graph; much faster in practice
Kuhn's matching O(V * E) bipartite only
Hopcroft-Karp matching O(E * sqrt(V)) bipartite only, faster still

Space is O(V + E) for the residual graph. In practice, Edmonds-Karp is fine for graphs with thousands of edges; contest-grade problems with larger graphs use Dinic's algorithm.

Common mistakes

  • Forgetting the reverse edges. Without them the algorithm cannot undo bad choices and may stop at a non-maximum flow. Create a reverse edge with capacity 0 for every edge you add.
  • Overwriting parallel edges. If two edges join the same pair of vertices, add their capacities (+=) instead of replacing one.
  • Treating undirected edges as one-way. An undirected edge of capacity c becomes two directed edges, each with capacity c.
  • Mixing up source and sink side when reading the min cut. The source side is the set reachable from s in the final residual graph.
  • Using DFS with big capacities and expecting good speed; prefer BFS (Edmonds-Karp) or Dinic.

Check your understanding

Quick check ยท 5 questions

of 5 answered You scored / 5 ยท perfect!

  1. 1. What does a backward edge in the residual graph represent?

    A backward edge v -> u with residual capacity f lets later augmenting paths reduce the flow on u -> v, undoing earlier choices.
  2. 2. What makes Edmonds-Karp different from plain Ford-Fulkerson?

    Choosing shortest augmenting paths bounds the number of augmentations by O(V * E), so the running time no longer depends on the capacity values.
  3. 3. The max-flow min-cut theorem says that:

    No flow can exceed any cut, and when augmenting paths run out the reachable set defines a cut whose capacity equals the flow.
  4. 4. How is maximum bipartite matching reduced to max flow?

    Capacity-1 edges at the source and sink ensure each vertex is used at most once, so an integer flow of value k is a matching of size k.
  5. 5. Why must we add a reverse edge with capacity 0 for every original edge?

    Pushing x along u -> v adds x to the capacity of v -> u, which only works if that entry exists.

Summary

  • A flow network has capacities, a source and a sink; a flow respects capacities and conserves flow at inner vertices.
  • The residual graph holds forward capacity c - f and backward capacity f, so augmenting paths can undo earlier decisions.
  • Ford-Fulkerson repeats "find augmenting path, push the bottleneck" until none exists; Edmonds-Karp uses BFS and runs in O(V * E^2).
  • Max flow equals min cut; the vertices reachable from the source in the final residual graph give a minimum cut.
  • Bipartite matching is max flow with unit capacities; Kuhn's DFS algorithm is the compact special case.
  • Always create reverse edges with capacity 0 and add capacities of parallel edges.

Next: Eulerian and Hamiltonian Paths